【Leetcode题单】（01 数组篇）刷题关键点总结02【统计数组中的元素】

【Leetcode题单】（01 数组篇）刷题关键点总结02【统计数组中的元素】（6题）

统计数组中的元素
- 645. 错误的集合 Easy
- 697. 数组的度 Easy
- 448. 找到所有数组中消失的数字 Easy
- 442. 数组中重复的数据 Medium
- 41. 缺失的第一个正数 Hard
- 274. H 指数 Medium

大家好，这里是新开的LeetCode刷题系列，以后尽量一天更新一个小章节。此系列应超过400题。
数组篇02《统计数组中的元素》，共6道题，3简单题2中等题1难题。
注意看重点部分，总结起来是这一类题的规律。

统计数组中的元素

645. 错误的集合 Easy

645. 错误的集合
在这里插入图片描述

public int[] findErrorNums(int[] nums) {
        int[] err = new int[2];
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for(int i = 1; i <= n; i++){
            if(map.getOrDefault(i, 0) == 2){
                err[0] = i;
            }else if(map.getOrDefault(i, 0) == 0){
                err[1] = i;
            }
        }
        return err;
    }

重点

Hashmap的getOrDefault的使用
标记错误数组
for循环 i 的范围
返回方式

697. 数组的度 Easy

697. 数组的度
在这里插入图片描述

	public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>(); // int[0] 出现次数，int[1] 起始位置，int[2]结束位置
        int maxTime = 0, minLength = nums.length;
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                int[] arr = new int[3];
                arr[0] = 1;
                arr[1] = i;
                arr[2] = i;
                map.put(nums[i], arr);
            } else {
                map.get(nums[i])[2] = i;
                map.get(nums[i])[0]++;
            }
            maxTime = Math.max(maxTime, map.get(nums[i])[0]);
        }
        for(int i = 0; i < nums.length; i++){
            if(map.get(nums[i])[0] == maxTime){
                minLength = Math.min(map.get(nums[i])[2] - map.get(nums[i])[1] + 1, minLength);
            }

        }
        return minLength;
    }

重点

HashMap中V设为数组
为HashMap的value赋值方法
HashMap的遍历

		for(Map.Entry<Integer, int[]> entry : map.entrySet()){
            int arr[] = entry.getValue();
            if(maxTime == arr[0]){
                minLength = Math.min(minLength, arr[2] - arr[1] + 1);
            }

        }

448. 找到所有数组中消失的数字 Easy

448. 找到所有数组中消失的数字
在这里插入图片描述

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> l = new ArrayList<Integer>();
        for(int num : nums){
            int cur = Math.abs(num);
            if(nums[cur - 1] > 0){
                nums[cur - 1] = -nums[cur - 1];
            }
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                l.add(i+1);
            }
        }
        return l;
    }

重点

原地修改：如果发现该位出现，则置为负
List <Integer> 的使用
使用负号做标志时，注意使用数组时将数据变为其绝对值
Math.abs()

442. 数组中重复的数据 Medium

442. 数组中重复的数据
在这里插入图片描述

    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;   
        List<Integer> l = new ArrayList<Integer>();
        for(int i = 0; i < n; i++){
            int x = Math.abs(nums[i]);
            if(nums[x - 1] > 0){
                nums[x - 1] = -nums[x - 1];
            }else{
                l.add(x);
            }
        }
        return l;
    }

重点

原地修改
- 如果发现该位出现一次，置为负数
- 再出现时判断正负，为负则出现两次
缩小使用空间的方式：改变数组本身
使用负号做标志时，注意使用数组时将数据变为其绝对值
Math.abs()

41. 缺失的第一个正数 Hard

41. 缺失的第一个正数
在这里插入图片描述

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i< n; i++){
            if(nums[i] <= 0){
                nums[i] = n + 1;
            }
        }
        for(int i = 0; i < n; i++){
            int cur = Math.abs(nums[i]);
            if(cur <= n){
                if(nums[cur - 1] > 0){
                    nums[cur - 1] = -nums[cur - 1];
                }
            }
        }
        for(int i = 0; i < n; i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        return n + 1;
    }

重点

缩小算法所用空间的常见方式，是改变数据本身进行操作
首先将无用数据抛弃：置为n+1，其次遍历，利用位置，置负操作
返回值的科学设置，即为算法跑完未产生答案时，默认的结果

274. H 指数 Medium

274. H 指数
在这里插入图片描述

    public int hIndex(int[] citations) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = citations.length, large = 0;
        for(int citation : citations){
            map.put(citation, map.getOrDefault(citation, 0) + 1);
            if(citation > n){
                large++;
            }
        }
        int h = large;
        for(int i = n; i >= 0; i--){
            h += map.getOrDefault(i, 0);
            if(h >= i){
                return i;
            }
        }
        return 0;
    }