leetcode14 Single Number

拼搏现实的明天。 2021-12-14 04:47 239阅读 0赞

Given a non-empty 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?
    
    Example 1:
    
    Input: [2,2,1]
    Output: 1
    Example 2:
    
    Input: [4,1,2,1,2]
    Output: 4

题目意思，给你一个非空的整形数组，每个元素出现两次，只有一个元素会出现一次，找出那个只出现一次的元素。

我的思路，把每个元素都放到map里面，如果该元素包含在map中，则把该元素从map中移除，进行下一个元素判断，这样最后map中的元素就只有一个元素，也就是题目所要求的那个数字。下面是我的实现：

class Solution {
        public int singleNumber(int[] nums) {
            if(nums == null || nums.length==0){
                return 0;
            }
            int len = nums.length;
            if(len == 1){
                return nums[0];
            }
            Map<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < len;i++) {
                if (map.containsKey(nums[i])){
                    map.remove(nums[i]);
                }else {
                    map.put(nums[i],nums[i]);
                }
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
               return  entry.getKey();
            }
            return  0;
        }
    }

Runtime: 8 ms, faster than 25.82% of Java online submissions for Single Number.
    Memory Usage: 40.7 MB, less than 40.15% of Java online submissions for Single Number.

然后去看了一下discuss，看到一个大佬的思路，很绝妙，使用`^`来解决问题，通过位操作也解决问题，举个例子：

如果0和某个值做位的异或运算，那么就会返回这个数  
a⊕0=a  
如果两个相同的数做异或运算，那么就会返回0  
a⊕a=0  
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b  
所以我们可以通过位运算来求里面那个独一的数字

代码实现如下：

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

Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number.
    Memory Usage: 41.7 MB, less than 20.73% of Java online submissions for Single Number.

下面这种解法是使用java8的新特性解决的，代码如下所示：

class Solution {
        public int singleNumber(int[] nums) {
            return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
        }
    }

Runtime: 37 ms, faster than 6.77% of Java online submissions for Single Number.
    Memory Usage: 39.1 MB, less than 60.87% of Java online submissions for Single Number.

感觉性能一般般吧，虽然代码很简洁，只有一行代码。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20211213/261c44bb83d14fd78761d066826024c9.png