Go 语言程序查找两个数组的并集

---

在 Go 语言中，就像其他编程语言一样，我们可以找到两个数组的并集。两个数组的并集是一个列表，其中包含数组 A 中的元素、数组 B 中的元素以及两个数组中共同存在的元素。

例如，我们有两个如下所示的数组

A = {2, 9, 5, 7, 3}

B = {5, 8, 7, 2, 1}

上述数组的并集将是

并集 = {1, 2, 3, 5, 7, 8, 9}

方法 1

在这种方法中，我们将找到两个未排序数组的并集。为此，我们将使用 Go 语言中的集合数据结构。此方法的时间复杂度为 O(n + m)，其中 n 和 m 是数组的大小。

算法

步骤 1：导入所有必需的包

步骤 2：声明 void 类型的结构体，然后创建一个 void 类型的变量。

步骤 3：定义 printArray() 函数，其中我们传递了数组及其大小，并使用循环打印数组值。

步骤 4：启动主函数。

• 声明并初始化两个数组 A 和 B。

• 创建一个集合，我们将向其中插入元素。集合具有仅存储唯一元素的属性，因此，如果在同一数组或两个数组中存在相同的元素，它将只存储该元素一次。

• 使用 printArray() 函数打印两个列表。

• 分别对两个数组运行 for 循环，并将元素追加到集合中。

• 最后，打印集合的所有元素。

示例

这是使用具有存储唯一元素属性的集合数据结构查找未排序数组的并集的代码。

package main

import "fmt"

// creating a void struct data type
type void struct{}

var member void

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
   for i := 0; i < size; i++ {
       fmt.Print(array[i], " ")
   }
   fmt.Println()
}

func main() {
   // declaring and initializing the slice
   // listA and listB of type int
   listA := []int{8, 4, 7, 1, 6}
   listB := []int{5, 3, 2, 3, 4, 7}

   //This is the way in Golang to create a set
   // using map where value is void=struct{}
   set := make(map[int]void)

   fmt.Print("List A: ")
   printArray(listA, 5)

   fmt.Print("List B: ")
   printArray(listB, 6)

   // running for loop over listA and adding all
   //The elements in the set
   for i := 0; i < 5; i++ {
       set[listA[i]] = member
   }

   // running for loop over listA and adding all
   //The elements in the set
   for i := 0; i < 6; i++ {
       set[listB[i]] = member
   }

   fmt.Print("The union of the above lists is: ")

   // printing all the keys of the set
   for k, _ := range set {
       fmt.Print(k, " ")
   }
   fmt.Println()
}

输出

List A: 8 4 7 1 6 
List B: 5 3 2 3 4 7 
The union of the above lists is: 3 2 8 4 7 1 6 5 

方法 2

在这种方法中，我们将找到两个未排序数组的并集，为此我们将对它们进行排序，然后相应地应用逻辑。此函数的时间复杂度将为 O((N + M)log(N+M))。

算法

步骤 1：导入所有必需的包。

步骤 2：声明 void 类型的结构体，然后创建一个 void 类型的变量。

步骤 3：定义 printArray() 函数，其中我们传递了数组及其大小，并使用循环打印数组值。

步骤 4：启动主函数。

• 声明并初始化两个数组 A 和 B。

• 使用 sort.Ints() 函数对两个数组进行排序。

• 通过传递数组及其大小作为参数来调用 unionOfSortedArrays() 函数。

步骤 5：unionOfSortedArrays() 函数的开始。

• 声明并初始化一个名为 unionArray 的数组，该数组将保存两个数组的并集。

• 遍历两个数组，并将一个数组的元素与另一个数组的元素进行比较，如果该元素尚未添加，则将其添加到 unionArray 中。

• 分别对两个数组运行单独的循环，并将这些元素添加到 unionArray 中。

示例

这是通过首先对未排序数组进行排序，然后遍历两个数组来查找其并集的代码。

package main

import (
    "fmt"
    "sort"
)

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

// unionOfSortedArray is a function with an array and
// integer as the argument and array, an integer as return type
func unionOfSortedArray(listA []int, sizeA int, listB []int, sizeB int) ([]int, int) {
    // declaring iterator variables and unionArray to store union values
    var unionArray []int
    var i, j int

    // declaring and initializing iterators
    i = 0
    j = 0

    // running for loop over both the arrays
    for i < sizeA && j < sizeB {
        // if element at index i in listA is less than equal to listB
        // then we are appending in unionArray if the last element is not
        // same
        if listA[i] <= listB[j] {
            if len(unionArray) == 0 || unionArray[len(unionArray)-1] != listA[i] {
                unionArray = append(unionArray, listA[i])
            }
            i++
        } else {
            if len(unionArray) == 0 || unionArray[len(unionArray)-1] != listB[j] {
                unionArray = append(unionArray, listB[j])
            }
            j++
        }
    }

    // iterating over listA if any element is uniterated
    for i < sizeA {
        if unionArray[len(unionArray)-1] != listA[i] {
            unionArray = append(unionArray, listA[i])
        }
        i++
    }

    // iterating over listB if any element is uniterated
    for j < sizeB {
        if unionArray[len(unionArray)-1] != listB[j] {
            unionArray = append(unionArray, listB[j])
        }
        j++
    }
    return unionArray, len(unionArray)
}

func main() {
    // declaring and initializing the slice
    // listA and listB of type int
    listA := []int{8, 4, 7, 1, 6}
    listB := []int{5, 3, 2, 3, 4, 7}

    fmt.Println("Golang program to find the union of two sorted arrays.")

    fmt.Print("List A: ")
    printArray(listA, 5)

    fmt.Print("List B: ")
    printArray(listB, 6)

    // sorting both the array in increasing order
    sort.Ints(listA)
    sort.Ints(listB)

    fmt.Println("Arrays after sorting")
    fmt.Print("List A: ")
    printArray(listA, 5)

    fmt.Print("List B: ")
    printArray(listB, 6)
    // calling function by passing both arrays and their size as an argument
    unionArray, size := unionOfSortedArray(listA, 5, listB, 6)

    fmt.Print("The union of the above lists is: ")
    printArray(unionArray, size)
}

输出

Golang program to find the union of two sorted arrays.
List A: 8 4 7 1 6 
List B: 5 3 2 3 4 7 
Arrays after sorting
List A: 1 4 6 7 8 
List B: 2 3 3 4 5 7 
The union of the above lists is: 1 2 3 4 5 6 7 8

结论

在本文中，我们探讨了如何在 Go 语言中查找已排序和未排序数组的并集。在第一种方法中，使用集合数据结构，我们减少了时间复杂度，但同时增加了空间复杂度。而在第二种方法中，我们使用排序算法，这增加了时间复杂度，但减少了空间复杂度。要了解有关 Go 语言的更多信息，您可以浏览这些教程。