算法通关村-----数组中元素出现次数问题

数组中出现次数超过一半的数字

问题描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。详见剑指offer39

问题分析

最直接的方式就是使用hashMap,遍历给定数组，将数字和对应出现次数存储在hashMap中，然后再遍历hashMap，找到出现次数最大的数字。除此之外，我们还可以将数据进行排序，升序和降序均可，排序后，出现次数超过一半的元素一定出现在数组的中位数位置。除此之外，还有一种巧妙解法，设立两个变量，num和count，num用于存储当前遍历到的元素，count用于存储次数,如果count为0，则当前元素不可能是出现次数超过一半的元素，则遍历下一个元素。

代码实现

使用HashMap解法

public int majorityElement(int[] nums) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++){
        if(map.containsKey(nums[i])){
            map.put(nums[i],map.get(nums[i])+1);
        }else{
            map.put(nums[i],1);
        }
    }
    int maxCount = Integer.MIN_VALUE;
    int maxNum = Integer.MIN_VALUE;
    for(int num:map.keySet()){
        if(map.get(num)>maxCount){
            maxCount = map.get(num);
            maxNum = num;
        }
    }
    return maxNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

使用排序解法

public int majorityElement(int[] nums) {
     Arrays.sort(nums);
     return nums[nums.length/2];
}
1
2
3
4

巧妙解法

public int majorityElement(int[] nums) {
    int result=0;
    int count=0;
    for(int num:nums){
        if(count==0){
            result = num;
        }
        count += result==num?1:-1;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11

数组中只出现一次的数字

问题描述

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

问题分析

使用HashMap存储数组元素和元素出现的次数，遍历HashMap，找到出现一次的元素,或者利用HashSet存储元素，利用集合的不可重复性，如果可以添加到集合中，说明当前遍历到的元素在数组中出现一次，直接添加，如果不能添加，说明当前遍历到的元素在数组中出现两次，移除HashSet中的当前元素，最后返回HashSet中的元素，即为数组中只出现一次的元素。除此之外，我们还可以利用位运算来实现。遍历数组元素，进行异或运算，出现两次的元素异或运算结果为0，所有元素的异或运算结果为数组中只出现一次的元素

代码实现

使用HashSet

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for(int num: nums){
        if(!set.add(num)){
           set.remove(num);
        }
    }
    Integer[] array = set.toArray(new Integer[set.size()]);
    return array[0];
}
1
2
3
4
5
6
7
8
9
10

使用异或运算

public int singleNumber(int[] nums) {
    int res = 0;
    for(int num:nums){
        res^=num;
    }
    return res;
}
1
2
3
4
5
6
7

137. 只出现一次的数字 II

问题描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

问题分析

使用HashMap存储数组元素和元素出现的次数，遍历HashMap，找到出现一次的元素。另外我们也可以使用位运算来实现对于出现3次的元素，每一位为0或者1,相加为0或者3，可以将每一位相加后对3取余，即为只出现一次的元素的对应位的值。

代码实现

使用位运算实现

public int singleNumber(int[] nums) {
    int res = 0;
    for(int i=0;i<32;i++){
        int total = 0;
        for(int num:nums){
            total+=((num>>i)&1);
        }
        if(total%3!=0){
            res |= (1<<i);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

元素出现次数问题通用方法就是使用HashMap存储元素和对应次数，或许遍历map即可得到想要出现次数的元素。这种方法需要遍历一次数组，遍历一次map，使用一个map，时间复杂度为O(n),空间复杂度为O(n)，面试时，可能不允许使用Hash或者集合，即需要我们设计O(n)时间复杂度,常数空间复杂度的算法。此时我们可以考虑常数计数或者为运算等常见方式。