X

LEETCODE 136. Single Number 解题思路分析

题目大意:

只出现一次的数字

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

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=136

解题思路分析:

本题实际上是异或运算的经典应用场景。在二进制运算中,两个不同的数字异或结果为1,相同数字的异或结果为0。如果在十进制数中,两个相同数字的异或依旧是0,而0和任意一个数的异或结果是那个任意的数字。

回到本题,因为题目中除了那个单独的数字之外都是两两相同的数字,因此除了单独数字之外的所有数字异或后的结果应该是0,而0和那个单独数字的异或结果就是那个单独的数字,也就是本题的返回结果。

所以本题的解法很简单,返回所有数字的异或结果即可。

实现代码:

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

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number.

Memory Usage: 40.2 MB, less than 94.07% of Java online submissions for Single Number.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-136-single-number-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)