Java解决数组的度问题

逃离我推掉我的手 2024-02-05 19:21 69阅读 0赞

## Java解决数组的度问题 ##

### 01 题目 ###

给定一个非空且只包含非负数的整数数组 `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 。

**提示：**

*  `nums.length` 在 `1` 到 `50,000` 范围内。
 *  `nums[i]` 是一个在 `0` 到 `49,999` 范围内的整数

### 02 知识点 ###

*  二维数组
 *  枚举

### 03 我的题解 ###

public class Text03 {
    	public static void main(String[] args) {
    //		测试
    		int[] nums= {49999,1,1,1,2,1};
    		System.out.println(findShortestSubArray(nums));
    	}
    	public static int findShortestSubArray(int[] nums) {
    //		记录数组，用二维数组来记录出现次数，起始点，终点
    		int[][] counts=new int[50001][3];
    		for (int i = 0; i < nums.length; i++) {
    //			每次循环出现次数+1，起始点值为0则改变，终点值也改变
    			counts[nums[i]][0]++;
    			if (counts[nums[i]][1]==0) {
    				counts[nums[i]][1]=i;
    			}
    			counts[nums[i]][2]=i;
    		}
    		//因为数组第一个的起始值会被覆盖，所以重新赋值
    		counts[nums[0]][1]=0;
    		int max=1;//出现的次数
    		int res=0;//返回值的下标
    //		循环整个数组找到出现次数最大的值所对应的下标
    		for (int i = 0; i < counts.length; i++) {
    			if (counts[i][0]>max) {
    				max=counts[i][0];
    				res=i;
    			}
    		}
    //		当出现次数最大后，比较始末状态对应的数组长度
    		for (int i = 0; i < counts.length; i++) {
    			if (counts[i][0]==max) {
    				if (counts[res][2]-counts[res][1]>counts[i][2]-counts[i][1]) {
    					System.out.println("i "+i);
    					res=i;
    				}
    			}
    		}
    //		返回值要额外+1
    		return counts[res][2]-counts[res][1]+1;
        }
    }