网站建设评估报告,建筑工程公司取名,口碑好网站制作公司哪家好,网站建设服务商排名题目描述
给定一个整数数组#xff0c;你需要寻找一个连续的子数组#xff0c;如果对这个子数组进行升序排序#xff0c;那么整个数组都会变为升序排序。
你找到的子数组应是最短的#xff0c;请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你…题目描述
给定一个整数数组你需要寻找一个连续的子数组如果对这个子数组进行升序排序那么整个数组都会变为升序排序。
你找到的子数组应是最短的请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。输入的数组可能包含重复元素 所以升序的意思是。
解法1排序
public int findUnsortedSubarray(int[] nums) {int[] arr Arrays.copyOf(nums, nums.length);Arrays.sort(arr);int start0,endnums.length-1;for(int i0;inums.length;i) {if(nums[i] ! arr[i]) {start i;break;}}for(int inums.length-1;i0;i--) {if(nums[i] ! arr[i]) {end i;break;}}if(start 0 arr[start] nums[start] end nums.length-1 arr[end] nums[end]) {return 0;}return end -start1;}解法2不排序
每次从左往右判断i(下标)位置是否比前i个的最大值大如果是则说明位置在这i 1中正确。假设不是则说明 位置不对因为从小到大i位置应该这i 1中最大才符合要求。不对记录下右边界索引如果后面都是比i位置大 正确排序则i就是最右的索引了。从右往左同理。
public int findUnsortedSubarray(int[] nums) {int max nums[0], min nums[nums.length-1], l -1, r -2;int len nums.length;for (int i 1; i len; i) {max Math.max(max, nums[i]);min Math.min(min, nums[len - 1 - i]);if (max ! nums[i]) {r i;}if (min ! nums[len - 1 - i]) {l len - 1 - i;}}return r - l 1;
}
