题目描述
在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。
返回重复了 N 次的那个元素。
示例:
输入:[5,1,5,2,5,3,5,4] 输出:5
提示:
4 <= A.length <= 10000 0 <= A[i] < 10000 A.length 为偶数
思路
1.从题目可以看出,数组中的元素要么出现了一次,要么出现了N次,所以我们可以使用一个Set存储遍历过的数字,若Set中已经存在该数字,它就是我们要找的答案。
Java代码实现
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { public int repeatedNTimes(int[] A) { Set<Integer> numSet = new HashSet<>(); for (int i = 0; i < A.length; i++) { if(numSet.contains(A[i])) return A[i]; else numSet.add(A[i]); } return -1; }
Golang代码实现
func repeatedNTimes(A []int) int { numMap := make(map[int]int) for i:=0;i<len(A);i++{ if _,ok := numMap[A[i]];ok{ return A[i] } numMap[A[i]] = i } return -1 }