跳转至

只出现一次的数字

最后更新：2023-12-02

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x21ib6/

题目描述

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

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

题目示例

输入： 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\)
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

思路

先排序，然后把数组分成两块，偶数位的一起，奇数位的一起，分别计算和。

因为题目中只有一个元素只出现一次，其他的元素都是出现两次。

那么先排输入个数是偶数的，这样只处理输入个数是奇数的。

分别计算和之后，奇数位肯定是比偶数位是要多计算一个数的，这样用奇数位的和-偶数位的和，就是我们需要的结果，防止有负数，千万不要取绝对值。

C
 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int singleNumber(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;
}
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 两个相同的数字，亦或之后结果为0
// 0与任何数组亦或的结果，为对应数字
int singleNumber(int* nums, int numsSize){
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        result = result ^ nums[i];
    }
    return result;
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func singleNumber(nums []int) int {
    stack := map[int]int{}
    for _, v := range nums {
        stack[v]++
    }

    for key, val := range stack {
        if val != 2 {
            return key
        }
    }
    return 0
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sort

func singleNumber(nums []int) int {
    n := len(nums)

    if n%2 == 0 {
        return 0
    }

    sort.Ints(nums)

    for index := 0; index < n; index++ {
        // 奇数，并且前面都匹配上了
        if index+1 >= n && n%2 != 0 {
            return nums[index]
        }

        if nums[index] != nums[index+1] {
            return nums[index]
        }
        index++
    }
    return 0
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import sort

func singleNumber(nums []int) int {
    n := len(nums)

    if n%2 == 0 {
        return 0
    }

    sort.Ints(nums)

    sumA, sumB := 0, 0
    for index := 0; index < n-1; index++ {
        sumA += nums[index]
        sumB += nums[index+1]
        index++
    }
    sumA += nums[n-1]

    return sumA - sumB
}
Go
1
2
3
4
5
6
7
8
9
// 两个相同的数字，亦或之后结果为0
// 0与任何数组亦或的结果，为对应数字
func singleNumber(nums []int) int {
    result := 0
    for _, v := range nums {
        result = result ^ v
    }
    return result
}