【简单】961. 重复 N 次的元素

题目

原题地址

在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。

返回重复了 N 次的那个元素。

示例 1:

1
2
输入:[1,2,3,3] 
输出:3

示例 2:

1
2
输入:[2,1,2,5,3,2] 
输出:2

示例 3:

1
2
输入:[5,1,5,2,5,3,5,4]
输出:5

提示:

1
2
3
4 <= A.length <= 10000
0 <= A[i] < 10000
A.length 为偶数

解题思路

这题的算法题目,主要是考我们的分析能力。

题目:在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。

  • 数组长度为 2N
  • 除重后有 N+1 个不同的数字
  • 有一个数字重复了N 次,其他的数字仅出现了一次,排除掉这个重复的数字,其他的数字只有 N

根据上述可以得到,只要有一个数字重复,就是结果需要返回的元素

参考代码

1、判断重复,用空间来换取时间, 来判断是否有重复

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func repeatedNTimes(A []int) int {
    n := uint(len(A) / 2)

    lists := make(map[int]uint, n+1)
    for _, v := range A {
        if _, ok := lists[v]; ok {
            lists[v]++
        } else {
            lists[v] = 1
        }
        if lists[v] == n {
            return v
        }
    }
    return -1
}

2、相邻的相同的元素之间的间隔,最多只能为1,否则就是最后一个与前面的相等

1
2
3
4
5
6
7
8
func repeatedNTimes(A []int) int {
    for i:=0;i<len(A)-2;i++{
        if A[i]==A[i+1]||A[i]==A[i+2]{
            return A[i]
        }
    }
    return A[len(A)-1] 
}