数组数字出现次数问题

找出数组中只出现一次的数字

给定一个非空整数数组,其中某个元素只出现一次,其余元素均出现两次。找出只出现一次的元素。

java
1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) { // 将所有数字异或,最终结果就是只出现一次的数字
result ^= num;
}
return result;
}

找出数组中只出现一次的两个数字

给定一个整数数组,其中有两个元素只出现一次,其余元素均出现两次。找出这两个只出现一次的元素。

java
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); // 找到最低位的1
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 的元素。

java
1
2
3
4
5
6
7
8
9
10
public int majorityElement(int[] nums) {  // 摩尔投票法
int candidate = 0, count = 0; // 维护一个候选数字 `candidate` 和计数器 `count`
for (int num : nums) {
if (count == 0) { // 更新 `candidate` 为当前数字
candidate = num;
}
count += (num == candidate) ? 1 : -1; // 如果当前数字等于 `candidate`,则 `count++`,否则 `count--`
}
return candidate;
}

找出数组中出现次数超过 n/3 的数字

给定一个大小为 (n) 的数组,找到所有出现次数超过 n/3 的元素。

java
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; // 维护两个候选数字 `candidate1` 和 `candidate2`,以及对应的计数器 `count1` 和 `count2`
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)),找出这个数字。

java
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) { // 统计每一位上 1 的个数
count++;
}
}
if (count % k != 0) { // 如果某位的统计结果不是 k 的倍数,则说明目标数字在该位为 1
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) 且仅使用常量额外空间

java
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; // 映射到[0,n-1]
if (nums[idx] > 0) { // 如果是正数,说明是第一次出现
nums[idx] *= -1;
} else { // 如果已经是负数,说明之前已经出现过一次
list.add(Math.abs(x));
}
}
return list;
}
}
java
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
// [4,3,2,7,8,2,3,1]
// [7,3,2,4,8,2,3,1]
// [3,3,2,4,8,2,7,1]
// [2,3,3,4,8,2,7,1]
// [3,2,3,4,8,2,7,1]
// [-3,2,3,4,8,2,7,1]
// [-3,2,3,4,1,2,7,8]
// [-3,2,3,4,1,-2,7,8]
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 只有 一个重复的整数 ,返回 这个重复的数 。

如果可以修改原数组,那么可以用和上一题类似的解答

java
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;
}
}
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// [1,3,4,2,2]
// [3,1,4,2,2]
// [2,1,4,3,2]
// [4,1,2,3,2]
// [2,1,2,3,4]
class Solution {
public int findDuplicate(int[] nums) { // 原地哈希,交换元素,使数组元素与索引对应
while (nums[0] != nums[nums[0]]) { // 交换nums[0]和nums[nums[0]],直到相等
int t = nums[nums[0]];
nums[nums[0]] = nums[0];
nums[0] = t;
}
return nums[0];
}
}

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

java
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++; // 找到小于等于mid的数的个数
if (cnt > mid) r = mid; // 如果个数大于mid,说明重复的数在左边
else l = mid + 1; // 否则在右边
}
return l;
}
}
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// [1,3,4,2,2]
// 0->1->3->2<->4
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;
}
}