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

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique elements.
• Exactly one element of nums is repeated n times.

Return the element that is repeated n times.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

---

其实就是找一个数组里重复出现的数字/出现次数超过一半的数字。最简单的做法就是用一个set存出现过的数字，如果有重复出现的就return。

class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (set.contains(i)) {
                return i;
            }
            set.add(i);
        }
        return -1;
    }
}

然后solutions里还有一种巧妙（并很难想）的解法。看了解答也看了老半天才看懂。它的思想大概是这样的：如果这个数组长度为2n，那么我们把它拆成n个两个一组的pair，那么要么就是每个pair里有一个我们要找的数字x，要么某个pair里就会两个都是x。假如是第一种情况，那么考虑到两个pair（也就是四个数字），最坏情况下就是x在第一个和最后一个，which is [x,a][b,x]。因此在所有情况下，每check连续的四个数字，如果有一个数字出现了两次，那这个数字就是x了。具体还能再简化成，只要check i和i - 1、i - 2这连续的三个数字就行，唯独只有上面列出的情况（which is x在第一个）才会有连续三个里都没有重复的的情况。

class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int i = 2; i < nums.length; i++) {
            if (nums[i - 2] == nums[i] || nums[i - 1] == nums[i]) {
                return nums[i];
            }
        }
        return nums[0];
    }
}