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语言的信息，您可以浏览这些教程。