给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。 请你找出满足题设的最短的子数组。 数据范围:数组长度满足 , 数组中的元素满足-笔试面试资料

这是qklbishe.com第19333 篇笔试面试资料
提供答案分析,通过本文《给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。
请你找出满足题设的最短的子数组。

数据范围:数组长度满足 , 数组中的元素满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。
请你找出满足题设的最短的子数组。

数据范围:数组长度满足 给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。          请你找出满足题设的最短的子数组。         数据范围:数组长度满足  , 数组中的元素满足 , 数组中的元素满足 给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。          请你找出满足题设的最短的子数组。         数据范围:数组长度满足  , 数组中的元素满足
Java

给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。          请你找出满足题设的最短的子数组。         数据范围:数组长度满足  , 数组中的元素满足 零葬

  1. 排序+双指针

排完序后用双指针比对了一下原始数组,然后找出无序部分的长度
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型一维数组       * @return int整型      */     public int findUnsortedSubarray (int[] nums) {         // write code here         int n = nums.length;         int[] rawNums = Arrays.copyOfRange(nums, 0, n);         Arrays.sort(nums);         int left = 0, right = n - 1;         while(left < n && rawNums[left] == nums[left]){             left++;         }         while(right >= 0 && rawNums[right] == nums[right]){             right--;         }         return Math.max(right - left + 1, 0);     } }

排序的时间复杂度为O(nlogn),后面双指针的时间复杂度为O(n),整体的时间复杂度为O(nlogn)。拷贝了原始数组,所以额外空间复杂度为O(n)。

利用单调性

如果某一个数nums[i]满足大于等于左边的最大值,小于等于右边的最小值,这个数在数组中就是不需要移动位置的。因此可以定出如下的算法流程:
  1. 从左往右遍历,如果nums[i]始终是nums[0:i]的最大值,就表示目前为止还是升序。如果碰到了不是最大值的情况,就记录位置,当前遇到了乱序。
  2. 从右往左遍历,如果nums[i]始终是nums[i:n-1]的最小值,就表示目前为止还是升序。如果碰到了不是最小值的情况,就记录位置,当前遇到了乱序。

而我们通过下标变换可以一遍循环就完成以上两步,根据步骤1能够得到无序的右边界,根据步骤2可以得到无序的左边界,进一步可以求得无序的长度。

class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型vector       * @return int整型      */     int findUnsortedSubarray(vector<int>& nums) {         int n = nums.size();         int leftMax = nums[0], rightMin = nums[n - 1], l = -1, r = -2;         for(int i = 1; i < n; i++){             leftMax = max(leftMax, nums[i]);                // nums[0:i]的最大值             rightMin = min(rightMin, nums[n - 1 - i]);      // nums[n-1-i:n-1]的最小值             if(leftMax != nums[i]){                 r = i;             }             if(rightMin != nums[n - 1 - i]){                 l = n - 1 - i;             }         }         return r - l + 1;     } };

只遍历了一遍数组,时间复杂度为O(n)。只使用了有限几个变量,空间复杂度为O(1)。

今天 14:41:07 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。 请你找出满足题设的最短的子数组。 数据范围:数组长度满足 , 数组中的元素满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情