力扣刷题练习——统计数组中的元素

目录

645. 错误的集合

697. 数组的度

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

442. 数组中重复的数据

41. 缺失的第一个正数

274. H 指数

---

645. 错误的集合

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

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

示例 2：

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

桶排思想

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n=nums.length;
        int[] num=new int[2];//储存结果
        int[] numss=new int[10005];//桶排
        for(int i=0;i//放入桶中
            int k=nums[i];
            numss[k]++;
        }
        for(int i=1;i<=n;i++){
            if(numss[i]==0){//缺少的
                num[1]=i;
            }
            if(numss[i]==2){//重复的
                num[0]=i;
            }
        }
        return num;
    }
}

697. 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

map

class Solution {
    public int findShortestSubArray(int[] nums) {
        //map映射key为数组元素，value有3个值（次数，第一次出现的位置，最后出现的位置）用int[]数组存储
        Mapint[]> map=new HashMapint[]>();
        int n=nums.length;
        //遍历数组
        for(int i=0;i
            //如果再次出现，次数加一，最后出现的位置更新
            if(map.containsKey(nums[i])){//map.containsKey判断key有没有出现过
                map.get(nums[i])[0]++;//map.get(nums[i])根据键获得值
                map.get(nums[i])[2]=i;
            }else{//第一次出现的存进来，次数初始化1，位置i，位置i；
                map.put(nums[i],new int[]{1,i,i});
            }
        }
        int maxx=0;
        int minn=0;
        //强遍历
        for(Map.Entryint[]> m:map.entrySet()){//map.entrySet获得所有键值对
            int[] num=m.getValue();//得到value数组
            if(num[0]>maxx){//比较次数
                maxx=num[0];
                minn=num[2]-num[1]+1;
            }else if(num[0]==maxx){//次数相等
                if(minn>num[2]-num[1]){//比较最短连续子数组，选择较小的存储
                    maxx=num[0];
                    minn=num[2]-num[1]+1;
                }
            }
        }
        return minn;
    }
}

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

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

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

错误思想：

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        List l=new ArrayList();
        for(int i=0;i
            if(nums[i]!=i+1){
                l.add(i+1);
            }
        }
        return l;
    }
}

 正确思想：

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        //存储结果
        List res=new ArrayList<>();
        //创建一个新的容器
        Set allNumber = new HashSet<>();
        //强循环将数组元素存到set中
        for(int num : nums){
            allNumber.add(num);
        }
        //通过循环，看看这个容器中有没有对应的值contains实现
        for(int i = 1;i <= nums.length;i++){
            if(!allNumber.contains(i)){
                //没有，就是消失的数，存进集合
                res.add(i);
            }
        }
        return res;
    }
}

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

示例 2：

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

示例 3：

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

class Solution {
    public List findDuplicates(int[] nums) {
        Arrays.sort(nums);
        List l=new ArrayList();
        for(int i=0;i1;i++){
            if(nums[i]==nums[i+1]){
                l.add(nums[i]);
            }
        }
        return l;
    }
}

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

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

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int temp=1;//用基准值和数组排序后的值进行比较
        for(int i=0;i
            if(nums[i]>0){//从数组为正数开始与基准值对比
                if(nums[i]==temp){
                    temp++;//该数存在基准值就加一
                }
            }else if(nums[i]<=0){
                continue;
            }
        }
        return temp;//返回最终更新好的基准值
    }
}

274. H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：
输入：
citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5次。
由于研究者有 3 篇论文每篇 至少 被引用了 3次，其余两篇论文每篇被引用 不多于 3次，所以她的 h 指数是3。

class Solution {
    public int hIndex(int[] citations) {
        //先排序
        Arrays.sort(citations);
        int n=citations.length;
        //排序后，对于某个i，就会有n - i篇论文的引用数 >= citations[i]，i篇论文的引用数 <= citations[i]
        for(int i=0;i
            //所以设k=n-i,至少有k篇论文引用数>= citations[i]
            int k=n-i;
            //当citations[i]>=k，就是结果
            if(citations[i]>=k){
                return k;
            }
        }
        return 0;
    }
    
}