数据机构与算法|Leetcode.581.最短无序连续子数组之HashMap真的好用 leetcode|数据结构|java|hashmap|算法

Leetcode.581.最短无序连续子数组之HashMap真的好用

前言
一、问题
- 1、分析问题
- 2、转换问题
- 3、写代码之前
- 4、写代码之后
三、算法评估
- 1、时间复杂度
- 2、空间复杂度
四、收获

前言

刷算法打卡中，抽到一个中等的题，但是你用HashMap就会非常简答。我们依旧是整理思路，不乱来，这样解题才快。

文章图片

一、问题 1、分析问题

输入一个无序数组，寻找最短无序数组，并返回个数。通过给数组排个序，找出变化的位置差就是最短无序数组。

2、转换问题

用Map将下标和数值存入，然后给value拍一个序，通过看对应的key值是否有对应的顺序来看最短无序数组在哪里。

3、写代码之前

public class FindUnsortedSubarray { public int findUnsortedSubarray(int[] nums) {/*分析问题 * 输入一个无序数组，寻找最短无序数组，并返回个数。 * 转换问题 * 用Map将下标和数值存入，然后给value拍一个序，通过看对应的key值是否有对应的顺序来看最短无序数组在哪里。 */ //1. 申请Map将数据的下标和数据存入 //2. 通过for循环比较小标与数据下标即Key是否相等，来计算最终的最短数组长度。 //3. 返回数组长度。 }

4、写代码之后

public class FindUnsortedSubarray { public int findUnsortedSubarray(int[] nums) {/*分析问题 * 输入一个无序数组，寻找最短无序数组，并返回个数。 * 转换问题 * 用Map将下标和数值存入，然后给value拍一个序，通过看对应的key值是否有对应的顺序来看最短无序数组在哪里。 */ //1. 申请Map将数据的下标和数据存入 Map m = new HashMap<>(); for(int i = 0; inew Integer(nums[j])); } //2. 通过for循环比较小标与数据下标即Key是否相等，来计算最终的最短数组长度。 List>list = new ArrayList>(m.entrySet()); list.sort((o1,o2)->o1.getValue().compareTo(o2.getValue())); int begin=-1,end=nums.length-1; for(int i = 0; ibegin; i--) {if(list.get(i).getKey() != i) {end = i; break; } } //3. 返回数组长度。 return begin==-1?0:end-begin+1; }

三、算法评估 1、时间复杂度