leetcode之只出现一次的数字

今天为大家分享的是关于在数组中找到只出现一次数字的系列题目，我将使用c跟Java来实现，希望我的分享能够帮助到大家。

文章目录

初阶查找单身狗
进阶找单身狗
小结

初阶查找单身狗

第一道题目是一个数组中只出有一个出现了一次的数字，也就是有一个单身狗。这是题目链接leetcode之只出现一次的数字

题目要求：
给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

理解题目

根据题目给出的要求我们可以知道这个题目要求我们写的代码时间复杂度不超过O(N),时间复杂度也不能超过O(N),也就是说我们要尽可能的做到遍历数组一遍并且不额外创建一个同样大小的数组来解决这个题目。

做题思路

在做这个题之前，我们需要知道一个知识，那就是异或(^)位运算。二进制位相同为0，相异为1。0异或任何数结果还是那个数，两个相同的数异或结果为0。也就是说这个题我们只需要将数组的每一个元素全部都异或一遍，得到的最终结果就是那个只出现了一次的数字。

C语言代码实现

int singleNumber(int* nums, int numsSize){
    int ret = 0;
    for(int i = 0;i<numsSize; i++)
    {
        ret^=nums[i];
    }
    return ret;
}

Java代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i<nums.length; i++) {
            ret^=nums[i];
        }

        return ret;
    }
}

这个题想必大家应该很容易理解吧，那么我们再来看一道进阶的找单身狗的问题。

进阶找单身狗

leedcode之只出现一次的数字（进阶）

题目要求

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

做题思路

这个题目跟上面其实思路是一样的，只不过在这个数组里面有两个只出现了一次的数字，我们还只是全部将他们异或一下，是不能得到最终结果的。所以这里我们需要稍稍做点改变，因为你数组里面如果只有一个单身狗，那么就是只需要全部异或一遍，那么如果数组里面有两个的时候我们只需要将两个只出现了一次的数字形象的放置在两个不同的数组中，其他两两相同的数字只需要在一个数组中就可以了。那么想要做出来这道题的关键其实就是如何将这两个只出现了一次的数字放在不同的数组中。

同样的我们还是先将这个数组的所有元素异或一下，这个异或的结果其实就是那两个只出现了一次的数字以获得结果。然后我们再来看这个结果的二进制位，因为我们前面说了，异或操作二进制位相同为0，相异为1，我们只需要找到二进制位1的地方，然后再将数组中所有元素相同的地方二进制位0的放一组，为1的放另一组，最后再分别异或就找到了那两个只出现了一次的数字。

C语言代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
    //动态开辟一个两个元素为0的数组，用来存放两个单身狗
    int* ans = (int*)calloc(2,sizeof(int));  
    int ret = 0;
    for(int i =0 ;i<numsSize; i++)
    {
        ret^=nums[i];
    }
    //pos用来记录ret中哪个二进制位为1
    int pos = 0;
    for(int i = 0; i<32; i++)
    {
        if((ret>>i)&1 == 1)
        {
            pos = i;
            break;
        }
    }
    for(int i = 0; i<numsSize; i++)
    {
        if((nums[i] >> pos)&1 == 1)
        {
            ans[0]^=nums[i];
        }
        else
        {
            ans[1]^=nums[i];
        }
    }

    *returnSize = 2;
    return ans;
}

Java代码实现

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] ans = new int[]{0,0};  
        int ret = 0;
        for(int i  =0; i<nums.length; i++) {
            ret^=nums[i];
        }
        int pos = 0;
        for(int i = 0; i<32; i++) {
            if(((ret>>i)&1) == 1) {
                pos = i;
                break;
            }
        }
        for(int i = 0; i<nums.length; i++) {
            if(((nums[i]>>pos)&1) == 1) {
                ans[0]^=nums[i];
            }else{
                ans[1]^=nums[i];
            }
        }
        return ans;
    }
}