Golang 查找两个数组的并集

在Golang中，像其他编程语言一样，我们可以找到两个数组的并集。两个数组的并集是由位于数组A中的元素和位于数组B中的元素以及同时位于两个数组中的共同元素组成的列表。

例如，我们有以下两个数组

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

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

上述数组的并集将为

Union = {1, 2, 3, 5, 7, 8, 9}

方法1

在这种方法中，我们将找到两个未排序数组的并集。为此，我们将使用Golang中的集合数据结构。该方法的时间复杂度为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： 开始main函数。

声明并初始化两个数组A和B。
使用sort.Ints()函数对两个数组进行排序。
通过传递数组和它们的大小作为参数来调用unionOfSortedArrays()函数。

步骤5： 开始unionOfSortedArrays()函数。
声明并初始化一个名为unionArray的数组，它将保存两个数组的并集。
使用for循环遍历两个数组，并将一个数组的元素与另一个数组的元素进行比较，如果该元素尚未添加到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