LeetCode 136. 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?

题意:一个数组中,只有一个数出现过一次,其它所有的数字都出现过两次,求哪个数出现过一次。

思路:第一种:用map统计哪个出现过一次
第二种:让所有数字异或,最后得到的结果,就是那个数字

java代码:

public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> dict = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (dict.containsKey(nums[i])) {
                dict.put(nums[i], dict.get(nums[i]) + 1);
            } else {
                dict.put(nums[i], 1);
            }
        }

        for(int i : dict.keySet()){
            if (dict.get(i) == 1) {
                return i;
            }
        }
        return 0;
    }

第二种:

public int singleNumber(int[] nums) {
        int result = 1;
        for(int i = 0;i<nums.length;i++){
            result ^= nums[i]; 
        }
        return result;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容