【LeetCode每日一题】——136.只出现一次的数字

一【题目类别】

• 数组

二【题目难度】

• 简单

三【题目编号】

• 136.只出现一次的数字

四【题目描述】

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

五【题目示例】

• 示例 1 ：

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

• 示例 2 ：

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

• 示例 3 ：

  • 输入：nums = [1]
  • 输出：1

六【解题思路】

• 这道题如果用哈希表做就很简单了，但是不符合题目要求的时间和空间复杂度
• 通过这个题可以学习到一个新的知识点：位运算。学过计算机组成原理应该都明白，首先有些性质我们要明白：
  • $a\oplus 0=a$：任何数和0做异或运算，结果仍然是原来的数
  • $a\oplus a=0$：任何数和其自身做异或运算，结果是0
  • $a\oplus b\oplus a=b\oplus a\oplus a=b\oplus (a\oplus a)=b\oplus 0=b$：异或运算满足交换律和结合律
• 通过以上性质就可以在题目要求的时空复杂度下完成此算法
• 首先定义数字0（res）
• 然后用0去异或数组的每一个值（从头到尾）
• 所有重复的数字都被过滤掉了
• 遍历完后只剩下出现一次的元素
• 最后返回结果即可

七【题目提示】

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

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为数组长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package Array;

/**
 * @Author: IronmanJay
 * @Description: 136.只出现一次的数字
 * @CreateTime: 2022-11-21  09:19
 */
public class p136_SingleNumber {

    public static void main(String[] args) {
        int[] nums = {2, 2, 1};
        int res = singleNumber(nums);
        System.out.println("res = " + res);
    }

    public static int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. C语言版

#include

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

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13

十【提交结果】

1. Java语言版
   

2. C语言版