You are given an integer array nums with the following properties:
nums.length == 2 * n.nums contains n + 1 unique elements.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 <= 5000nums.length == 2 * n0 <= nums[i] <= 104nums 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];
- }
- }