数组数字出现次数问题

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

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

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

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 的元素。

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)），找出这个数字。

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) 且仅使用常量额外空间

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;
    }
}
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 只有 一个重复的整数 ，返回 这个重复的数 。

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

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
// [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) 的额外空间。

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;
    }
}
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;
    }
}