只出现一次的数字Ⅰ¶

最后更新：2024年09月20日

链接：

题目描述

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

题目示例

示例 1：示例 2：示例 3：

输入： nums = [2,2,1]

输出： 1

输入： nums = [4,1,2,1,2]

输出： 4

输入： nums = [1]

输出： 1

提示：

\(1 <= nums.length <= 3 * 10^4\)
\(-3 * 10^4 <= nums[i] <= 3 * 10^4\)
除了某个元素只出现一次以外，其余每个元素均出现两次。

题解

位运算出栈入栈数组

利用位运算的特性，因为输入的数组是整数数组，整数的位运算有如下特点：

按位与（AND）：比特位数字都为1，结果为1，否则为0。如：0xff | 0x08 = 0x08; 0xf0 | 0x84 = 0x80
按位或（OR）：比特位数字有一个为1，结果为1，否则为0。如：0x80 | 0x08 = 0x88; 0x70 | 0x84 = 0xf4
按位异或（XOR）：比特位数字不同，则为1，否则为0。如：0x18 | 0x08 = 0x10; 0x10 | 0x14 = 0x04
按位非（NOT）：按位取反操作。如：~0xff = 0x00; ~0x01 = 0xfe

按照如上原理，如果两个整数数字相同，在按位异或之后，结果为0，即a^a = 0。

按照题目的条件，输入的数字中除了某个元素只出现一次外，其他的每个元素均出现两次，那么所有的数组按位异或的结果将是只出现了一次的那个数字。即a^b^c^d^c^b^a = d

利用栈的特性，同一个数字，第一次入栈，再次遇到时出栈。最终栈里面就会剩下只出现一次的数字

这个就是利用数组的方法了：

利用哈希表，记录每个数字出现的次数，然后便利哈希表，得到只出现一次的数字。
排序，计算偶数位和奇数位数字之和，然后计算差值，就可以得到只出现一次的数字。

位运算解法

C异或Go异或C++异或Python异或Rust异或

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

Go
func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result = result ^ num
    }
    return result
}

C++
#include "vector"

using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result = result ^ num;
        }
        return result;
    }
};

Python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in list:
            result = result ^ num
        return result

Rust
impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut result = 0;
        for num in nums {
            result = result ^ num
        }
        return result
    }
}

数组解法计算奇偶位差值

C差值Go差值C++差值Python差值Rust差值

C
int* compForSingleNumber(const void *a, const void *b) {
    return (int *) (*(int *) b - *(int *) a);
}

int singleNumber1(int* nums, int numsSize){
    if (numsSize %2 == 0) {
        return 0;
    }

    int numa = 0;
    int numb = 0;

    qsort(nums,numsSize,sizeof(int),compForSingleNumber);
    for (int i = 0; i < numsSize - 1; i++) {
        numa += nums[i++];
        numb += nums[i];
    }
    numa += nums[numsSize - 1];

    return numa - numb;
}

Go
func singleNumber(nums []int) int {
    if len(nums) % 2 == 0 {
        return 0
    }

    sort.Ints(nums)
    numa := 0
    numb := 0
    println(numa, numb, len(nums))
    for i := 0; i < len(nums) - 1; i++ {
        numa += nums[i]
        numb += nums[i + 1]
        i += 1
    }
    numa += nums[len(nums) - 1]
    return numa - numb
}

C++
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int numa = 0;
        int numb = 0;
        for (int i = 0; i < nums.size() -1; ++i)
        {
            numa += nums[i];
            numb += nums[i + 1];
            i++;
        }
        numa += nums[nums.size() - 1];
        return numa - numb;
    }
};

Python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        numa,numb = 0,0
        nums.sort()
        flags = True
        for num in nums:
            if flags:
                numa += num
            else:
                numb += num
            flags = not flags
        return numa - numb

Rust
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        numa,numb = 0,0
        nums.sort()
        flags = True
        for num in nums:
            if flags:
                numa += num
            else:
                numb += num
            flags = not flags
        return numa - numb

C语言的栈解法

C
int comp(const void *a, const void *b) {
    if (*(int*)a > *(int*)b) {
        return 1;
    }
    return -1;
}

int singleNumber(int* nums, int numsSize) {
    unsigned int top = 0;
    if ((numsSize == 0) || (numsSize %2 == 0)) {
        return 0;
    }

    if (numsSize == 1) {
        return nums[0];
    }
    qsort(nums, numsSize, sizeof(int), comp);

    int* stack = (int*)malloc(4 * sizeof(int));
    if (stack == NULL) {
        return 0;
    }
    (void)memset(stack, 0, 4 * sizeof(int));
    stack[top] = -100000000;

    for (int i = 0; i < numsSize; i++) {
        if (stack[top] == nums[i]) {
            top--;
            continue;
        }
        top++;
        stack[top] = nums[i];
    }
    if (top > 1) {
        return 0;
    }
    int result = stack[1];
    free(stack);
    return result;
}