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 語言的更多資訊，您可以瀏覽這些教程。