首页 > 其他 > 详细

136. Single Number

时间:2020-04-07 15:06:32      阅读:51      评论:0      收藏:0      [点我收藏+]

136. Single Number
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

题解

第一种:将数据存到一个list中,相同的就remove掉

class Solution {
    public int singleNumber(int[] nums) {
        List<Integer> no_duplicate_list = new ArrayList();
        
        for (int i : nums) {
            if (no_duplicate_list.contains(i)) {
                no_duplicate_list.remove(new Integer(i));
                continue;
            }
            
            no_duplicate_list.add(i);
            
        }
        
        return no_duplicate_list.get(0);
        
    }
}

复杂度分析

时间复杂度:O(n^2)O(n 2) 。我们遍历 \text{nums}nums 花费 O(n)O(n) 的时间。我们还要在列表中遍历判断是否存在这个数字,花费 O(n)O(n) 的时间,所以总循环时间为 O(n^2)O(n 2) 。
空间复杂度:O(n)O(n) 。我们需要一个大小为 nn 的列表保存所有的 \text{nums}nums 中元素。

第二种:用map,还是一样,有的删除,没有的put

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> no_duplicate_map = new HashMap<>();
        
        for (int i : nums) {
            
            if (null == no_duplicate_map.get(i)) {
                no_duplicate_map.put(i, 1);
                continue;
            }
           
            no_duplicate_map.remove(i);
            
        }
        
        for (int i : nums) {
            if (no_duplicate_map.get(i) != null && no_duplicate_map.get(i) == 1) {
                return i;
            }
            
            continue;
            
        }
        
        return 0;
        
    }
}

第三种:2?(a+b+c)?(a+a+b+b+c)=c

这种仅仅适用于本题目,只有最多只会出现两次,最少出现一次,且出现一次的只能有一个这种情况

class Solution {
    public int singleNumber(int[] nums) {
       int sumOfSet = 0;
        int sumOfNums = 0;
        Set<Integer> set = new HashSet<>();
        
        for (int i : nums){
            if (!set.contains(i)) {
                set.add(i);
                sumOfSet += i;
            }
            
            sumOfNums += i;
        }
        
        return 2 * sumOfSet - sumOfNums;
        
    }
}

第四种:异或

如果我们对 0 和二进制位做 XOR 运算,得到的仍然是这个二进制位
a⊕0=a
如果我们对相同的二进制位做 XOR 运算,返回的结果是 0
aa=0
XOR 满足交换律和结合律
aba=(aa)⊕b=0⊕b=b

天呐,这都是些什么人

都是神仙嘛?

怎么能想出来的。。。

class Solution {
    public int singleNumber(int[] nums) {
       int a = 0;
        
        for (int i : nums) {
            a ^= i;
        }
        
        return a;
        
    }
}

136. Single Number

原文:https://www.cnblogs.com/zhangqian27/p/12653353.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!