leetcode排序169多数元素

leetcode排序169多数元素

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

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

示例 1：

输入：[3,2,3]
输出：3
示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

思路1：hashmap

public class majorityelement {
    public int majorityElement(int[] nums) {
        int result = nums[0];
        HashMap map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(nums[i])){
                map.put(nums[i], 1);
            }else {
                Integer value = map.get(nums[i]);
                map.put(nums[i], ++value);
            }
        }
        Set> entries = map.entrySet();
        for (Map.Entry entry : entries) {
            if (entry.getValue() > nums.length/2){
                result = entry.getKey();
            }
        }
        return result;
    }
}

注意点：

通过value获取key：map.entrySet() 可以获得一个keyvalue迭代器entries，遍历迭代器，对每一个entry，可以通过 entry.getKey() 和 entry.getValue() 分别获得 key 和 value

另外一种方式：

遍历keyset，拿到key，再拿到value，判断value

for (Integer key : map.keySet()){
            if (map.get(key) > nums.length/2){
                return key;
            }
}

思路2：排序+双指针（针对于出现次数最多的元素）

定义快慢指针，初始时均在最左侧
循环遍历数组
    判断快慢指针值是否相等
        如果相等，快指针前进一步，慢指针不动，计算快慢指针差值，并更新最大差值和最大元素值
        如果不相等，快指针前进一步，并将慢指针移动至快指针相同位置

public class majorityelement {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int slow = 0;
        int fast = 0;
        int maxvalue = nums[0];
        int maxlength = 0;
        while (fast < nums.length){
            if (nums[fast] == nums[slow]){
                if ((fast-slow)>=maxlength){
                    maxlength = fast-slow;
                    maxvalue = nums[fast];
                }
            }else {
                slow = fast;
            }
            fast++;
        }
        return maxvalue;
    }
}