刷题日记03

难呀，今天这题难呀，直接写的太麻烦了。看了题解发现最容易想出来的方法暴力映射超出了时间限制，其次最容易想出来的是用HashMap做的。

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

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

我先复盘一下我自己最初的思路，我是这么想的，先进行排序，得到升序序列[1,1,1,2,2,2,2]。然后我定义一个Set和一个List分别为set和list，再定义一个计数变量count = 1。遍历数组，假如当前元素a[i]和后一个元素a[i+1]相等，我就在Set中存放a[i]，因为这说明a[i]这个数不止一个，是一个潜在的多数，因此要把计数count加1。这里用Set是因为其不能存储重复元素，即使add()了重复元素对Set集合也不产生改变，所以Set的作用就是存储出现次数大于1的元素。

注意的是这个Set必须是LinkedHashSet，因为这种Set元素的排序是按照存入顺序排列的，我原来就是用HashSet，但我发现有时候输出结果不对，调试的时候就发现是因为set和list没对应上，就是因为set的顺序不对。

如果a[i] != a[i+1]，就说明a[i]这个数以及计数完毕，下一个新的数来了，就需要先判断count是否大于1，如果大于1就说明上一个数出现多次，就要把出现次数count存储到集合list中，然后再把count复原，开始记录下一个数。

for (int i = 0; i < nums.length - 1; i++) {
     if(nums[i] == nums[i+1]){
         set.add(nums[i]);
         count++;
     }else {
         //先判断count是否等于1，如果不等于1，说明这个nums[i]出现了超过一次，就需要把出现次数
         //存储到list2中，然后复原count
         if (count != 1){
             list.add(count);
             count = 1;
         }
     }
}
list.add(count);

这么写最坑的就是我最后还要写一句list.add(count)，因为不写的话，例如[1,1,1,2,2,2,2]这样的，最后这个2的count无法存入到list中，是因为遍历索引的问题，看看有没有大神能够帮我优化一下。然后执行下面代码，找到了题目要求的多数

Integer max = Collections.max(list);
int index = list.indexOf(max);
List<Integer> setlist = new ArrayList<>(set);
Integer result = setlist.get(index);

我排序代码这次用的是归并，上次用的是快速，把之前学的高级排序都复习复习。下面是我整体代码

class Solution {
    private static int[] assist;
    public int majorityElement(int[] nums) {
        sort(nums);
        //用来存储nums中出现的次数超过1次的元素
        Set<Integer> set = new LinkedHashSet<>();
        //List<Integer> list1 = new ArrayList<>();
        //用来存储nums中出现的次数超过1次的元素的个数，和arr1对应
        List<Integer> list = new ArrayList<>();
        //计数，用来计nums中不出现的次数超过1次的元素的个数，然后存在arr2中
        int count = 1;

        if (nums.length == 1){
            return nums[0];
        }
        //遍历nums数组
        for (int i = 0; i < nums.length - 1; i++) {
            if(nums[i] == nums[i+1]){
                set.add(nums[i]);
                count++;
            }else {
                //先判断count是否等于1，如果不等于1，说明这个nums[i]出现了超过一次，就需要把出现次数
                //存储到list2中，然后复原count
                if (count != 1){
                    list.add(count);
                    count = 1;
                }
            }
        }
        list.add(count);
        System.out.println(set);
        System.out.println(list);
        Integer max = Collections.max(list);
        int index = list.indexOf(max);
        List<Integer> setlist = new ArrayList<>(set);
        Integer result = setlist.get(index);
        System.out.println(result);
        return result;
    }
    //排序
    public static void sort(int[] nums){
        assist = new int[nums.length];
        int lo = 0;
        int hi = nums.length - 1;
        sort(nums,lo,hi);
    }
    //范围内排序
    public static void sort(int[] nums,int lo,int hi){
        if (lo >= hi){
            return;
        }

        int mid = lo + (hi - lo)/2;
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        //归并
        merge(nums,lo,mid,hi);
    }
    /*
    归并，lo到mid一组，mid+1到hi一组，对这两组数据进行合并
     */
    public static void merge(int[] num,int lo,int mid,int hi){
        //lo到mid数组和mid+1hi数组归并到assist辅助数组中
        int i = lo;//assist的指针，从头开始
        int p1 = lo;//左数组指针第一个元素
        int p2 = mid + 1;//右数组指针第一个元素

        //比较左右两个数组元素大小，哪个小就把哪个数存入到assist中
        while (p1 <= mid && p2 <= hi){
            if(less(num[p1],num[p2])){
                assist[i++] = num[p1++];
            }else {
                assist[i++] = num[p2++];
            }
        }

        //在一边数组全部填充好了之后就可填充另一个
        while (p1 <= mid){
            assist[i++] = num[p1++];
        }
        while (p2 <= hi){
            assist[i++] = num[p2++];
        }

        //拷贝
        for (int j = lo;j <= hi;j++){
            num[j] = assist[j];
        }
    }
    //比较大小
    public static boolean less(Integer v,Integer w){
        return v.compareTo(w) < 0;
    }

    //交换
    public static void exch(int[] a,int i,int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

根据此题题解，我知道可以用HashMap来做，键用来存数字，值用来存出现的次数。如果第一个元素是2，我们就可以去集合中看看这个2是否存在，如果不存在，是第一次出现，就往集合中添加2和1就行，表示2出现了1次了。如果第二元素也是2，还要去集合中判断一下，已经存在了，把值加1，以此类推。把所有数字以及出现次数都存入到HashMap中后，进行遍历，得到max，用打擂台的方式。最后再进行一次遍历，找到max对应的键。即为出现最多的数字。附上找最大值的代码，排序方法同上。

public int majorityElement(int[] nums) {
        sort(nums);
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(hashMap.containsKey(nums[i])){
                //如果这个键已经存在，就把之前的值取出来然后加一
                int count = hashMap.get(nums[i]);
                count++;
                hashMap.put(nums[i],count);
            }else {
                //这个数不存在，添加进入作为键，值就是1
                hashMap.put(nums[i],1);
            }
        }

        //设最大值为0
        int max = 0;
        //遍历map，找出最大值
        Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            int value = entry.getValue();
            if (value > max){
                max = value;
            }
        }
        System.out.println(hashMap);
        System.out.println(max);
        //找到最大值对应的键
        Integer key = 0;
        for (Map.Entry<Integer, Integer> entry : entries) {
            int value = entry.getValue();
            if(value == max){
                key = entry.getKey();
            }
        }
        return key;
    }

这题真是花费我好久时间，先把自己想的整出来了，再去学学Map，不过收获颇丰，不枉我花费时间。