Golang 查找N+1数组中的重复元素

在编程中，有一个问题被问到面试中，要求在大小为N+1的数组中找到重复的数字。而且，数组中只有一个重复的元素。元素的范围是1到N。

例如,

数组 = {1,3,2,1,4}

上述数组中的重复元素是1。

步骤

步骤1: 使用import关键字在顶部导入所需的包。

步骤2: 然后主函数将首先运行。

首先，我们声明和初始化数组。
现在，我们调用函数找到重复的元素。
最后，我们打印重复的元素。

方法1

在这种方法中，我们将创建一个独立的函数，在函数中我们将在数组上运行一个嵌套的for循环，并将每个元素与其他元素进行比较。每当我们找到相同的元素时，我们返回该元素并从函数中返回。该方法的时间复杂度是O(N*N)，其中N是数组的大小。

示例

这是通过在数组上运行嵌套循环来查找数组中的重复元素的代码。在每次迭代中，我们检查索引i处的元素是否与索引j处的元素匹配。

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.

方法2

在此方法中，我们在单独的函数中创建了一个映射数据结构。如您所知，在映射中，我们可以将元素存储为键和值的形式，其中值是唯一的。在此情况下，键将是int类型，而值将是bool类型。创建映射后，我们将通过运行for循环迭代数组，并通过将值设置为true来存储元素，每当我们发现当前元素的值在映射中已经为true时，我们将返回该值。这种方法的时间复杂度将小于先前的方法，即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 {
    // 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.

方法3

从时间和空间的角度来说，这种方法比之前的两种方法都要好，因为我们在这里使用了找到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.