Single Number
程序员文章站
2022-05-02 19:09:33
...
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
给定一个数组,每个元素都出现了两次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素。我们可以采取位运算,两个相同的数异或结果为0,任何数异或0都为它本身,因此我们只需要将数组中的数全部进行异或运算最后的结果就是出现一次的数,这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
给定一个数组,每个元素都出现了两次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素。我们可以采取位运算,两个相同的数异或结果为0,任何数异或0都为它本身,因此我们只需要将数组中的数全部进行异或运算最后的结果就是出现一次的数,这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
public class Solution { public int singleNumber(int[] nums) { if(nums == null) return -1; int result = 0; for(int i = 0; i < nums.length; i++) result ^= nums[i]; return result; } }
上一篇: Single Number II
下一篇: 为啥要用位运算代替取模呢