济南 网站建设,短链接生成接口,安徽省建设工程信息网企业入口在哪,石家庄房产网官网java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 方法一#xff1a;hash表 此方法是工作中时间可以使用的#xff0c;因为…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 方法一hash表 此方法是工作中时间可以使用的因为它的时间和空间复杂度都相对平衡也较低。下面介绍的方法二工作中是坚决不可以使用的因为会造成大量的空间浪费。 解题思路 先遍历一遍数组记录每个元素的出现次数起始下标和结尾下标然后遍历hash表找到最大出现次数的元素然后通过len 结尾下标 - 起始下标 1获取其长度如果遇到相同出现次数的元素选择长度更小的作为答案题目要求 代码:时间复杂度O(n) 空间复杂度O(n) class Solution {public int findShortestSubArray(int[] nums) {//哈希表key为nums数组中的元素值。value为int数组共3个元素保存当前key的[度,起始下标,结尾下标]MapInteger, int[] map new HashMapInteger, int[]();int n nums.length;//数组长度for(int i 0;i n ; i){if(map.containsKey(nums[i])){//如果当前map已经有该数字map.get(nums[i])[0];//当前数字的出现次数1map.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.EntryInteger, 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(minLenarr[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 minInteger.MAX_VALUE;//保存数组中元素的最小值int maxInteger.MIN_VALUE;//保存数组中元素的最大值//获取最大最小值for(int i: nums){maxMath.max(max,i);minMath.min(min,i);}int[] countnew int[max-min1];//建立数组数组下标对应nums元素的取值范围空间复杂度会非常高int maxCount0;//找到元素的最大出现次数//找到最大次数for(int i:nums){//依次遍历数组元素//以当前元素 - min 作为下标让count数组对应值1代表这个值出现了一次//因为数组下标从0开始count[0]代表nums数组的最小值i - min就是count对应下标maxCountMath.max(maxCount,count[i-min]);//保存出现次数最大的}if(maxCount1){//如果最大出现次数为1直接返回1return 1;}/****否则需要寻找出现次数最大也就是 maxCount的元素然后获取其起始和末尾下标 */int resnums.length;int start,endnums.length-1;int num0;//寻找for(int i0;icount.length;i){if(count[i]!maxCount){continue;}start0;endnums.length-1;nummini;while(startendnums[start]!num){start;}while(startendnums[end]!num){end--;}resMath.min(res,end-start1);}return res;}
}
