leetcode: Single Number

问题描述：

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?

原问题链接：https://leetcode.com/problems/single-number/

 

问题分析

　　这个问题的解决思路相对来说就比较简单了。只是用到了一个小的技巧。如果能想到的话就没什么了。在问题描述中说到，数组中所有元素都出现两次，除了一个元素。而这里就是要找这个独特的元素。那么有没有什么办法找到这个元素呢？

　　一种理想的情况就是我通过一次遍历，能够使得所有重复出现的元素都被消去了，只留下这个独特的元素。这个时候，如果我们借用一个位运算的小技巧，比如异或运算，那么就可以得到这个结果了。因为对于两个相同的元素来说，它们的异或运算结果就是0。所以我们对里面所有的元素按照这个方式遍历一遍，就可以得到最终的结果。

　　详细的代码实现如下：

 

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

 

评论

4 楼 frank-liu 2016-07-05  

mfkvfn 写道

frank-liu 写道

mfkvfn 写道

你这逻辑有问题好吧。
你用数组[1,2,3]运行一下结果看看。结果是0，但是所有的数字只出现了1次。

另外你的题目里要求“找出所有只出现了一次有数字”，你的代码结果是“数组中是不是存在没出现2次的数字”。文不对题，况且结果还是错误的。

这是问题的描述：
Given an array of integers, every element appears twice except for one. Find that single one.
它的意思是说给定一组整数，每个元素会出现两次，除了一个元素。就是说，它给的前提条件就是不包含你说的[1, 2, 3]这种情况。而且只会有一个只出现一次的元素。

那你可以用[1,1,2,2,3]测试一下看看。

你没看明白问题的描述和我代码的意思。你跑一下我的程序看看，看你用[1, 1, 2, 2, 3]的结果是不是返回３。

3 楼 mfkvfn 2016-07-05  

frank-liu 写道

mfkvfn 写道

你这逻辑有问题好吧。
你用数组[1,2,3]运行一下结果看看。结果是0，但是所有的数字只出现了1次。

另外你的题目里要求“找出所有只出现了一次有数字”，你的代码结果是“数组中是不是存在没出现2次的数字”。文不对题，况且结果还是错误的。

这是问题的描述：
Given an array of integers, every element appears twice except for one. Find that single one.
它的意思是说给定一组整数，每个元素会出现两次，除了一个元素。就是说，它给的前提条件就是不包含你说的[1, 2, 3]这种情况。而且只会有一个只出现一次的元素。

那你可以用[1,1,2,2,3]测试一下看看。

2 楼 frank-liu 2016-07-05  

mfkvfn 写道

你这逻辑有问题好吧。
你用数组[1,2,3]运行一下结果看看。结果是0，但是所有的数字只出现了1次。

另外你的题目里要求“找出所有只出现了一次有数字”，你的代码结果是“数组中是不是存在没出现2次的数字”。文不对题，况且结果还是错误的。

这是问题的描述：
Given an array of integers, every element appears twice except for one. Find that single one.
它的意思是说给定一组整数，每个元素会出现两次，除了一个元素。就是说，它给的前提条件就是不包含你说的[1, 2, 3]这种情况。而且只会有一个只出现一次的元素。

1 楼 mfkvfn 2016-07-05  

你这逻辑有问题好吧。
你用数组[1,2,3]运行一下结果看看。结果是0，但是所有的数字只出现了1次。

另外你的题目里要求“找出所有只出现了一次有数字”，你的代码结果是“数组中是不是存在没出现2次的数字”。文不对题，况且结果还是错误的。