算法练习- LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数

95 阅读 0 评论 63 点赞

我是靠谱客的博主有魅力枕头，这篇文章主要介绍算法练习- LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数，现在分享给大家，希望可以做个参考。

今日心情：生活在慢慢走上正轨，慢慢走总能达到想去的地方。

题目描述：

LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数

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

解题代码：（满足题目对于时间和空间复杂度要求的解法：异或+位判断）

复制代码

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
31
32
33
class Solution {

    //使用 异或进位

    public int[] singleNumbers(int[] nums) {
        
        //获取划分两组的
        int th = 0;
        for(int num:nums){
            th ^= num;
        }

        //找到最低位进行划分
        // 1. 相同的划分到同一组
        // 2. 不同的划分到不同组
        int div = 1;
        while((th & div) == 0){
            div <<= 1;
        }

        int group1 = 0;
        int group2 = 0;

        for(int num: nums){
            if((num & div) != 0){
                group1 ^= num;
            }else{
                group2 ^= num;
            }
        }
        return new int[]{group1,group2}; 
    }
}

解题代码：（自己首先拿到题的时候想的，但是不满足题目对于空间复杂度的要求：HashMap）

复制代码

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
class Solution {

    //使用 map 记录可以实现（但是不满足题目空间复杂度的要求）

    public int[] singleNumbers(int[] nums) {

        HashMap<Integer,Boolean> map= new HashMap<>();
        LinkedList<Integer> arr = new LinkedList<>();

        for(int num: nums){
            map.put(num,!map.containsKey(num));
        }

        for(int num:nums){
            if(map.get(num)){
                arr.add(num);
            }
        }
        int len = arr.size();
        int[] res = new int[len];
        for(int i=0;i<len;i++){
            res[i] = arr.get(i);
        }
        return res;
    }
}

解题思路：

自己首先拿到题的时候想到就是用HashMap进行记录然后找没有重复的，满足时间复杂度O（n）但是不满足空间复杂度O（1）的要求。然后想不出来就直接看题解，看如何进行操作能否达到要求的空间复杂度，题解用的就是位操作的方法。所以看两个数相不相同除了可以用==比较，也可以用异或进行比较，相同为0，不同为1。0 异或任何数为该数本身。

题解方法：

（1）要找出这两个只出现一次的数字，如果数组全部进行异或，那么最后的异或结果就是那两个只出现一次的数字。所以这两个不同的数字的区别信息其实就在他们的异或结果之中，题解的方法很巧妙，使用的异或结果中的最低为1的位来将数组划分为不同的两个组，划分的要求是将相同的数划分在同一个组中，不同的数分别在两个组中，这样分别对两个组里的所有数进行异或操作，最后的结果就是要找的不同的数。

（2）首先对数组中所有的数进行异或，得到的异或结果就是两个不同数的异或结果，因为其他的数都有重复异或结果为0，0异或其他数的结果为该数的本身。

（3）获得异或结果之后，找最低位为1（div）：div起始为1，找th的最低位，div 与 th 进行位与如果为0 则进行左移，否则找到了th的最低位。

（4）通过 div 将数组划分为两个组分别进行异或，因为div 是两个不同数字的异或结果所以可以直接通过 div 区分两个不同数组，如果div 与 num 进行位与，结果为1 划分到 group1 进行异或，如果为 0 划分到 group2进行异或。因为相同数的位相同，所以通过div 可以直接划分到同一组中，div 本身就是用来区别不同数字的所以，不同数组会被分别划分到group1和group2。

（5）返回 group1 和 group2 的异或结果就是这两个不同数。