美文网首页
剑指 Offer 56 - I 数组中数字出现的次数

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

作者: itbird01 | 来源:发表于2022-01-12 11:01 被阅读0次
    题目.png

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

    解题思路

    解法1:
    1.直接使用hashset的不可重复性,由于数组的元素出现两次的有若干组,出现一次的有两个
    2.那么我们在hashset添加过程中,如果发现相同的,则及时移除,这样的话,hashset一直会占用常量级别(实际上最大为4)的存储空间

    解法2:

    特性:
    a^a=0
    a^0=a
    abc=acb
    a&(-a)=最低位为1的二进制(从右到左)

    1.先对所有数字进行一次异或,得到两个出现一次的数字的异或值
    2.在异或结果中找到任意为 11 的位
    3.根据这一位对所有的数字进行分组
    4.在每个组内进行异或操作,得到两个数字

    解题遇到的问题

    后续需要总结学习的知识点

    ##解法1
    import java.util.HashSet;
    import java.util.Iterator;
    
    class Solution {
        public int[] singleNumbers(int[] nums) {
            if (nums.length <= 2) {
                return nums;
            }
            HashSet<Integer> set = new HashSet<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (set.contains(nums[i])) {
                    set.remove(nums[i]);
                } else {
                    set.add(nums[i]);
                }
            }
            Iterator<Integer> iterator = set.iterator();
            int[] ans = new int[set.size()];
            int i = 0;
            while (iterator.hasNext()) {
                ans[i++] = iterator.next();
            }
            return ans;
        }
    }
    
    ##解法2
    class Solution {
        public int[] singleNumbers(int[] nums) {
            if (nums.length <= 2) {
                return nums;
            }
            int res = 0;
            for (int i : nums) {
                res ^= i;
            }
    
            int flag = res & -res;
            int num1 = 0, num2 = 0;
            for (int i : nums) {
                if ((i & flag) == 0) {
                    num1 ^= i;
                } else {
                    num2 ^= i;
                }
            }
            return new int[]{num1, num2};
        }
    }
    

    相关文章

      网友评论

          本文标题:剑指 Offer 56 - I 数组中数字出现的次数

          本文链接:https://www.haomeiwen.com/subject/jikpqrtx.html