leetcode解题之数组中数字出现的次数

63 阅读 0 评论 42 点赞

我是靠谱客的博主彪壮花瓣，最近开发中收集的这篇文章主要介绍leetcode解题之数组中数字出现的次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一个整型数组 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）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的方法是先排序，然后再比较相邻的元素

class Solution {
    public int[] singleNumbers(int[] nums) {
        int len = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        for(int i=0;i<len-1;i++){
            if(nums[i]==nums[i+1]){
                i++;
            }else{
                list.add(nums[i]);
            }
            if(i==len-2){
                list.add(nums[len-1]);
            }
        }
        int[] res = new int[2];
        for(int i=0;i<2;i++){
            res[i]=list.get(i);
        }
        return res;
    }
}

经典的解法是使用异或运算符，异或运算符的特性为：
1、(a^b) ^c= a^ (b^c) ;
2、a^b=1;
3、a^a=0;
4、a^0=a;
相同的数异或为0，不同的异或为1。0和任何数异或等于这个数本身。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int sum = 0;
        for(int num:nums){
            sum^=num;
        }
        int flag=(-sum)&sum;//为了区分两个数的标识
        int[] res = new int[2];
        for(int num:nums){
            if((flag&num)==0){
                res[0]^=num;
            }else{
                res[1]^=num;
            }
        }
        return res;
    }
}