当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.剑指offer.056.数组中数字出现的次数

LeetCode.剑指offer.056.数组中数字出现的次数

题目描述

《剑指offer》面试题56 - I. 数组中数字出现的次数
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

260 Single Number III
https://leetcode-cn.com/problems/single-number-iii/

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

限制: 2 <= nums <= 10000


相似题目

LeetCode.136.Single Number 数组中只出现一次的数
LeetCode.137.Single Number II 数组中只出现一次的数2
LeetCode.260.Single Number III 数组中只出现一次的数3
LeetCode.剑指offer.056.数组中数字出现的次数


解题过程

一看题有印象做过,貌似是用位运算,但具体怎么做已经忘了,想了一会儿想出来了。
看来做题还是有用的,即便忘了也比没做过要强。

假如只出现一次的数为 a 和 b
思路是想一个办法把 a,b 拆分到两个数组中,然后变成了2个其他元素出现2次只有一个出现一次的子问题,直接异或即可。

怎么才能把 a,b 区分开呢?
我们求所有元素的异或值,则结果是 a^b ,因为所有其他元素都两两消掉了,因为 a 和 b 肯定不相同,所以 a^b 不是0,则可以用 a^b 的二进制表示的某个值是1的位来把 a b 区分开,

比如可以取 a^b 的最低位1,则
1、对于a,b来说,肯定在这个二进制位上是不同的,因为异或的计算规则是相同为0,不同为1
2、对于所有其他两两元素来说,相同的2个数在这个二进制位上肯定是相同的

具体实现上
我们利用公式 lowbit(i) = i & -i; 得到 a^b 的保留最低位1其余全为0对应的整数,则
数组中所有元素和 lowbit 进行 按位与的结果等于 lowbit 的是一组,不等于 lowbit 的是另一组,
则a,b肯定在这两个不同组中,对这两组所有元素分别异或,分别得到的就是a,b的值

时间复杂度 O(n),空间复杂度 O(1)

private static class SolutionV2020 {
    public int[] singleNumbers(int[] nums) {
        if (null == nums || nums.length < 2) {
            return nums;
        }
        // 所有元素的异或,就等于出现1次的两个数的异或
        int xor = nums[0];
        for (int i = 1; i < nums.length; i++) {
            xor ^= nums[i];
        }
        // 获取 xor 的最低位1其余全0对应的整数,牢记这个公式
        int lowest1 = xor & (-xor);
        // 根据 nums[i] 在 lowest1 位上是1还是0把数组中的数分为2组同时做异或,出现次数为1的两个数肯定在不同组中,其他的相同的元素肯定在同一组中
        int group1 = 0, group2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((lowest1 & nums[i]) == lowest1) {
                group1 ^= nums[i];
            } else {
                group2 ^= nums[i];
            }
        }
        return new int[] {group1, group2};
    }
}

GitHub代码

algorithms/leetcode/offer/_056_TwoSingleNumber.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_056_TwoSingleNumber.java


上一篇 LeetCode.1095.Find in Mountain Array 山脉数组中查找目标值

下一篇 LeetCode.023.Merge k Sorted Lists 合并K个排序链表

阅读
评论
816
阅读预计3分钟
创建日期 2020-04-28
修改日期 2020-04-28
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论