Go語言程式查詢N+1大小陣列中的重複元素

---

在程式設計中，面試中經常會遇到一個問題：在一個大小為N+1的陣列中查詢重複的數字。而且，陣列中只有一個重複元素。元素範圍在1到N之間。

例如：

陣列 = {1,3,2,1,4}

上述陣列中1是重複元素。

演算法

步驟1： 使用`import`關鍵字匯入所需的包。

步驟2： 然後`main`函式將首先執行。

• 首先，我們宣告並初始化陣列。

• 現在，我們呼叫函式來查詢重複元素。

• 最後，我們列印重複元素。

方法一

在這個方法中，我們將建立一個單獨的函式，在這個函式中，我們將對陣列執行巢狀的for迴圈，並將每個元素與其他元素進行比較。每當我們找到相同的元素時，我們都返回該元素，並從函式中返回。

示例

這是透過對陣列執行巢狀迴圈來查詢陣列中重複元素的程式碼。

package main

import "fmt"

// 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 duplicateElement(array []int, size int) int {
    // running nested for loop to compare every element with each other
    for i := 0; i < size; i++ {
        for j := i + 1; j < size; j++ {
            // if the element at index i is equal to the element at index j
            //Then we are returning the duplicate element
            if array[i] == array[j] {
                return array[i]
            }
        }
    }
    return -1
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find duplicate elements in an N+1 size array using nested for loop.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

輸出

Golang program to find duplicate elements in an N+1 size array using nested for loop.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

方法二

在這個方法中，在單獨的函式中，我們建立一個map資料結構。眾所周知，在map中，我們可以以鍵值對的形式儲存元素，其中值是唯一的。在這種情況下，鍵將是int型別，值將是bool型別。建立map之後，我們將透過執行for迴圈迭代陣列，並在每次發現當前元素的值在map中已經為true時儲存元素並將值設定為true，然後我們將返回值。這種方法的時間複雜度將小於前一種方法，即O(N)，但空間複雜度將增加，因為我們使用了map。

示例

這是透過建立map資料結構並將元素儲存在其中來查詢陣列中重複元素的程式碼，如果計數變為2，則返回該元素。

package main

import "fmt"

// 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 duplicateElement(array []int, size int) int {
    // creating a map using the make function
    // where int is key and bool is value
    mapDuplicate := make(map[int]bool)

    // running for loop over the array
    for i := 0; i < size; i++ {
        // checking that array[i] is true or false in the map
        if mapDuplicate[array[i]] {
            return array[i]
        }
        mapDuplicate[array[i]] = true
    }
    return -1
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find a duplicate element in an N+1 size array using the map data structure.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

輸出

Golang program to find a duplicate element in an N+1 size array using the map data structure.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

方法三

這種方法在時間和空間方面都比前兩種方法更好，因為這裡我們使用的是求N個數之和的數學公式，然後求陣列中所有元素之和。最後，所有元素之和與N個數之和的差將返回重複數字的值。時間複雜度為O(N)，不使用額外的空間。

示例

這是使用求陣列和的數學公式來查詢陣列中重複元素的程式碼。

package main

import "fmt"

// 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 duplicateElement(array []int, size int) int {
    // declaring the variables using the var keyword
    var sum1, sum2 int

    sum1 = 0

    // using Maths formula to find the sum of N numbers
    sum2 = ((size - 1) * (size)) / 2
    // running for loop over the array
    for i := 0; i < size; i++ {
        // find the sum of all the elements of the array
        sum1 = sum1 + array[i]
    }

    // as the sum1 will more then sum2 which is equal to the extra element
    return sum1 - sum2
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find duplicate elements in an N+1 size array using a math formula to find the sum of N numbers.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

輸出

Golang program to find duplicate elements in an N+1 size array using a math formula to find the sum of N numbers.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

結論

這三種方法都是查詢N+1個元素陣列中重複元素的方法，這些元素來自1到N的集合。在這三種方法中，第三種方法效率最高，因為它不使用額外的空間，並且時間複雜度為O(N)。要了解更多關於Go語言的資訊，您可以瀏覽這些教程。