java数据结构与算法刷题-----LeetCode697. 数组的度

发布时间:2024年01月24日
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

在这里插入图片描述

方法一:hash表

此方法是工作中时间可以使用的,因为它的时间和空间复杂度都相对平衡,也较低。下面介绍的方法二,工作中是坚决不可以使用的,因为会造成大量的空间浪费。

解题思路
  1. 先遍历一遍数组,记录每个元素的出现次数,起始下标和结尾下标
  2. 然后遍历hash表,找到最大出现次数的元素,然后通过len = 结尾下标 - 起始下标 +1获取其长度
  3. 如果遇到相同出现次数的元素,选择长度更小的作为答案(题目要求)
代码:时间复杂度O(n) 空间复杂度O(n)

在这里插入图片描述

class Solution {
    public int findShortestSubArray(int[] nums) {
        //哈希表,key为nums数组中的元素值。value为int数组,共3个元素保存当前key的[度,起始下标,结尾下标]
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        int n = nums.length;//数组长度
        for(int i = 0;i < n ; i++){
            if(map.containsKey(nums[i])){//如果当前map已经有该数字
                map.get(nums[i])[0]++;//当前数字的出现次数+1
                map.get(nums[i])[2] = i;//当前数字出现的末尾下标
            }else map.put(nums[i],new int[]{1,i,i});//第一次遇到就放入map,出现次数为1,起始下标为i,结尾下标为i
        }
        int maxNum = 0, minLen = 0;//maxNum保存拥有最大的度的元素,minLen保存,包含最大度的所有元素且尽可能短的数组长度
        for(Map.Entry<Integer, int[]> entry: map.entrySet()){
            int[] arr = entry.getValue();
            if(maxNum < arr[0]){//如果当前保存的 元素的度, 没有当前遍历元素的度大
                maxNum = arr[0];//就保留大的度,也就是当前遍历元素的这个,更大的度
                minLen = arr[2] - arr[1] +1;//更新子数组长度
            }else if(maxNum == arr[0]){//如果两个元素的度相同,
                //我们保留更短的子数组长度
                if(minLen>arr[2] - arr[1] + 1) minLen = arr[2] - arr[1] +1;
            }
        }
        return minLen;//根据题意,返回包含度最大所有元素的最短子数组长度
    }
}

方法二:数组下标线性索引

此方法的做题效率更高,对于某些题目来说,确实无论是实际应用和做题的角度来说,都是不错的方法。但不是这道题应该使用的方法。对于这道题也只能做题时可以使用一下了。因为它用数组中的值的范围,作为数组x的下标,数组x作为hash表,来进行常数级的存取。但是假设,数组中存储的元素范围是1 ~ 100000000,那么就需要申请长度为100000000的数组空间。假设有一个数组需要处理,[1,2,3,4,4,4,10000000000],如果使用正经的hash表,只需要7个空间。而使用这种方法,空间复杂度就是10000000000。如果实际应用场景你写出这种代码,100%会被辞退的。因此,这个方法,对于这道题,只能大家做题使用,千万不要放到工作场景中。

时间复杂度O(n), 空间复杂度O(maxValue - minValue + 1),空间复杂度是数组中值的取值范围。真的了解一下即可,不推荐使用,纯粹在投机取巧

在这里插入图片描述

class Solution {
    /**此方法空间复杂度过高,不推荐工作场景下使用,假设nums = [1,2,2,10000000000] 那么空间复杂度就是 10000000000,
    * 而hash表空间复杂度是4.
    */
    public int findShortestSubArray(int[] nums) {
        /** 首先,先建立一个数组,用下标来表示nums中所有元素的值。最大值-最小值 +1 就是nums的value值范围 */
        int min=Integer.MAX_VALUE;//保存数组中元素的最小值
        int max=Integer.MIN_VALUE;//保存数组中元素的最大值
        //获取最大最小值
        for(int i: nums){
            max=Math.max(max,i);
            min=Math.min(min,i);
        }
        int[] count=new int[max-min+1];//建立数组,数组下标对应nums元素的取值范围,空间复杂度会非常高
        int maxCount=0;//找到元素的最大出现次数
        //找到最大次数
        for(int i:nums){//依次遍历数组元素
            //以当前元素 - min 作为下标,让count数组对应值+1,代表这个值出现了一次
            //因为数组下标从0开始,count[0]代表nums数组的最小值,i - min就是count对应下标
            maxCount=Math.max(maxCount,++count[i-min]);//保存出现次数最大的
        }
        if(maxCount==1){//如果最大出现次数为1,直接返回1
            return 1;
        }
        /****否则需要寻找出现次数最大(也就是 == maxCount)的元素,然后获取其起始和末尾下标 */
        int res=nums.length;
        int start,end=nums.length-1;
        int num=0;
        //寻找
        for(int i=0;i<count.length;i++){
            if(count[i]!=maxCount){
                continue;
            }
            start=0;
            end=nums.length-1;
            num=min+i;
            while(start<end&&nums[start]!=num){
                start++;
            }
            while(start<end&&nums[end]!=num){
                end--;
            }
            res=Math.min(res,end-start+1);
        }
        return res;
    }
}
文章来源:https://blog.csdn.net/grd_java/article/details/135815466
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。