数组数字出现次数问题
找出数组中只出现一次的数字
给定一个非空整数数组,其中某个元素只出现一次,其余元素均出现两次。找出只出现一次的元素。
1 2 3 4 5 6 7 public int singleNumber (int [] nums) { int result = 0 ; for (int num : nums) { result ^= num; } return result; }
找出数组中只出现一次的两个数字
给定一个整数数组,其中有两个元素只出现一次,其余元素均出现两次。找出这两个只出现一次的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int [] singleNumber(int [] nums) { int xor = 0 ; for (int num : nums) { xor ^= num; } int mask = xor & (-xor); int num1 = 0 , num2 = 0 ; for (int num : nums) { if ((num & mask) == 0 ) { num1 ^= num; } else { num2 ^= num; } } return new int []{num1, num2}; }
找出数组中出现次数超过一半的数字
给定一个大小为 (n) 的数组,找到出现次数超过 n/2
的元素。
1 2 3 4 5 6 7 8 9 10 public int majorityElement (int [] nums) { int candidate = 0 , count = 0 ; for (int num : nums) { if (count == 0 ) { candidate = num; } count += (num == candidate) ? 1 : -1 ; } return candidate; }
找出数组中出现次数超过 n/3
的数字
给定一个大小为 (n) 的数组,找到所有出现次数超过 n/3
的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public List<Integer> majorityElement (int [] nums) { int candidate1 = 0 , candidate2 = 0 , count1 = 0 , count2 = 0 ; for (int num : nums) { if (num == candidate1) { count1++; } else if (num == candidate2) { count2++; } else if (count1 == 0 ) { candidate1 = num; count1 = 1 ; } else if (count2 == 0 ) { candidate2 = num; count2 = 1 ; } else { count1--; count2--; } } count1 = 0 ; count2 = 0 ; for (int num : nums) { if (num == candidate1) count1++; if (num == candidate2) count2++; } List<Integer> result = new ArrayList <>(); if (count1 > nums.length / 3 ) result.add(candidate1); if (count2 > nums.length / 3 ) result.add(candidate2); return result; }
找出数组中出现次数为指定次数的数字
给定一个数组,其中某些数字出现 k
次,只有一个数字出现 m
次((m \neq k)),找出这个数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int findNumber (int [] nums, int k, int m) { int result = 0 ; for (int i = 0 ; i < 32 ; i++) { int count = 0 ; for (int num : nums) { if ((num >> i & 1 ) == 1 ) { count++; } } if (count % k != 0 ) { result |= (1 << i); } } return result; }
总结
问题
解法
时间复杂度
空间复杂度
只出现一次的数字
异或运算
(O(n))
(O(1))
只出现一次的两个数字
分组异或
(O(n))
(O(1))
出现次数超过一半的数字
摩尔投票法
(O(n))
(O(1))
出现次数超过 (n/3) 的数字
摩尔投票法扩展
(O(n))
(O(1))
出现次数为指定次数的数字
位统计
(O(n))
(O(1))
数组中重复的数据
给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 最多两次 。请你找出所有出现 两次 的整数,并以数组形式返回。要求时间复杂度为 O(n) 且仅使用常量额外空间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public List<Integer> findDuplicates (int [] nums) { ArrayList<Integer> list = new ArrayList <>(); for (int x : nums) { int idx = Math.abs(x) - 1 ; if (nums[idx] > 0 ) { nums[idx] *= -1 ; } else { list.add(Math.abs(x)); } } return list; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public List<Integer> findDuplicates (int [] nums) { List<Integer> ans = new ArrayList <>(); int n = nums.length; for (int i = 0 ; i < n; i++) { int t = nums[i]; if (t < 0 || t - 1 == i) continue ; if (nums[t - 1 ] == t) { ans.add(t); nums[i] *= -1 ; } else { int c = nums[t - 1 ]; nums[t - 1 ] = t; nums[i--] = c; } } return ans; } }
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
如果可以修改原数组,那么可以用和上一题类似的解答
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int findDuplicate (int [] nums) { for (int x : nums) { int idx = Math.abs(x); if (nums[idx] > 0 ) { nums[idx] *= -1 ; } else { return idx; } } return -1 ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int findDuplicate (int [] nums) { while (nums[0 ] != nums[nums[0 ]]) { int t = nums[nums[0 ]]; nums[nums[0 ]] = nums[0 ]; nums[0 ] = t; } return nums[0 ]; } }
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int findDuplicate (int [] nums) { int n = nums.length; int l = 1 , r = n; while (l < r) { int mid = l + (r-l)/2 ; int cnt = 0 ; for (int x : nums) if (x <= mid) cnt++; if (cnt > mid) r = mid; else l = mid + 1 ; } return l; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int findDuplicate (int [] nums) { int slow = 0 , fast = 0 ; do { slow = nums[slow]; fast = nums[fast]; fast = nums[fast]; } while (slow != fast); slow = 0 ; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }