从今天开始用java刷题。

只出现一次的数字

问题描述

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

说明：

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

题解

hash表

附加知识点：

Map集合基于 键（key）/值（value）映射。每个键最多只能映射一个值。键可以是任何引用数据类型的值，不可重复；值可以是任何引用数据类型的值，可以重复；键值对存放无序。

HashMap常用方法：
put(K key, V value) ：将键（key）/值（value）映射存放到Map集合中。
get(Object key) ：返回指定键所映射的值，没有该key对应的值则返回 null。
size() ：返回Map集合中数据数量。
clear() ：清空Map集合。
isEmpty () ：判断Map集合中是否有数据，如果没有则返回true，否则返回false。
remove(Object key) ：删除Map集合中键为key的数据并返回其所对应value值。
values() ：返回Map集合中所有value组成的以Collection数据类型格式数据。
keySet() ：返回Map集合中所有key组成的Set集合。
containsKey(Object key) ：判断集合中是否包含指定键，包含返回 true，否则返回false。
containsValue(Object value) ：判断集合中是否包含指定值，包含返回 true，否则返回false。
entrySet() ：将Map集合每个key-value转换为一个Entry对象并返回由所有的Entry对象组成的Set集合。

Java遍历Map的4种方式

算法思想1：

遍历数组，一边统计数据出现的次数，一边将数据作为键，出现次数作为值存进hash表；遍历hash表，返回值为1对应的键。

代码1：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(Integer num :nums){//foreach语句：num == nums[i]
            Integer count = map.get(num);//在map中查找num
            count = count == null ? 1 : ++count;//若count为null，即没找到则令count=1,否则count的值加1
            map.put(num,count);
        }
        for(Integer num : map.keySet()){//遍历map
            if(map.get(num) == 1)
                return num;
        }
        return 0;
    }
}

算法思想2：

遍历数组，将数组元素作为键存入map，每次存入前先查找map中是否有相同值，若有，则移除；若无，则存入。最后map中仅存的元素即为所求。

代码2：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(Integer num :nums){//foreach语句：num == nums[i]
            Integer count = map.get(num);//在map中查找num
            if(count != null)
                map.remove(num);
            else
                map.put(num,1);
        }
        for(Integer num : map.keySet())//因为map是无序的，所以只能遍历取值
            return num;
        return 0;
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

位运算

附加知识点：

异或运算的性质：

1. a ⊕ 0 = a ;
2. a ⊕ a = 0 ;
3. 异或运算满足交换律和结合律。

算法思想：将数组中的所有元素进行异或运算，因为出现过两次的数亦或结果为0，0和0亦或结果还是0，最后0和只出现过一次的数亦或出来就是那个数。

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

时间复杂度：O（n）
空间复杂度：O（1）

多数元素

问题描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

题解

hash表

算法思想：

利用hash表统计各个元素出现的次数，返回出现次数大于⌊ n/2 ⌋ 的元素。

代码：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(Integer num:nums){//计数
            Integer count = map.get(num);
            count = count == null ? 1 : ++count;
            map.put(num,count);
        }
        for(Integer num:map.keySet()){//返回
            Integer n = nums.length;
            if(map.get(num) > n/2)
                return num;
        }
        return 0;
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

排序

算法思想：

因为多数元素的个数大于n/2，所以将数组排序后的第n/2个元素一定是多数元素。

代码：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        return nums[n/2];
    }
}

时间复杂度：O（nlogn）
空间复杂度：O（1）

Boyer-Moore 投票算法

投票算法的思想就是：

候选人初始为nums[0]，票数初始为1，遍历数组，遇到相同数则候选人票数+1，遇到不同数则候选人票数-1，当候选人的票数为0时则更换候选人并初始化票数。遍历完数组后当前候选人即最终答案。

原理：

因为多数元素的个数是大于n/2的，所以当其与其他数相消时，它的票数一定会大于1，因而存留到最后。

代码：

class Solution {
    public int majorityElement(int[] nums) {
       int res = nums[0];//res表示候选人
       int tikets = 1;
       for(int num : nums){
           if(num == res)
            tikets++;
            else tikets --;
            if(tikets == 0){
                res = num;
                tikets = 1;
            }
       }
       return res;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

心得

最近刷题有点囫囵吞枣了，还是得静下心来细嚼慢咽呀~

最后

以上就是拉长蜜粉为你收集整理的【35】只出现一次的数字 | 多数元素（LC 136 | 169）只出现一次的数字多数元素心得的全部内容，希望文章能够帮你解决【35】只出现一次的数字 | 多数元素（LC 136 | 169）只出现一次的数字多数元素心得所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。