[LeetCode]961. N-Repeated Element in Size 2N Array

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：405 字 | 阅读时长：2 分钟

961. N-Repeated Element in Size 2N Array

Easy

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

1
2
Input: [1,2,3,3]
Output: 3

Example 2:

1
2
Input: [2,1,2,5,3,2]
Output: 2

Example 3:

1
2
Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. A.length is even

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int n = A.size()/2;
        map<int, int> item_map;
        int target;
        for (int item : A) {
            if (item_map.count(item)) {
                if (++item_map[item] == n) {
                    target = item;
                    break;
                }
            } else {
                item_map.insert(make_pair(item, 1));
            }
        }
        return target;
    }
};

result

Runtime: 88 ms, faster than 8.10% of C++ online submissions for N-Repeated Element in Size 2N Array.

Memory Usage: 17.4 MB, less than 6.23% of C++ online submissions for N-Repeated Element in Size 2N Array.

方法二

审题啊，审题，审题不详细，代码写再多也是枉然，题目中明确说明，只有一个数字是重复的，其他都是唯一的，这个时候用set最好解决了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        set<int> item_set;
        int target;
        for (int item : A) {
            if (item_set.count(item)) {
                return item;
            } else {
                item_set.insert(item);
            }
        }
        return -1;
    }
};

result

Runtime: 40 ms, faster than 88.98% of C++ online submissions for N-Repeated Element in Size 2N Array.

Memory Usage: 10.8 MB, less than 68.86% of C++ online submissions for N-Repeated Element in Size 2N Array.

效果显著，但是不是特别好。

逛一下讨论区，看看网友们的奇技淫巧：

https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208563/JavaC%2B%2BPython-O(1)-Solution

这个作者的方法二和方法三，实在是令人惊叹。