LeeCode
【题目描述】
给你一个整数数组 nums
,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组,并输出它的长度。
https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/?favorite=2cktkvj
【示例】
【代码】admin
思路: 要找中间的无须序列, 最简单的就是对比排序前后, begin和end的下标即可
package com.company;
import java.util.*;
// 2022-02-13
class Solution {
public int findUnsortedSubarray(int[] nums) {
// 复制一下原数组
int[] arr = Arrays.copyOf(nums, nums.length);
// 记录下标用
int begin = 0;
int end = 0;
// 原数组排序
Arrays.sort(nums);
// 从前往后, 新旧数组对比, 记录初始值
for (int i = 0; i < nums.length; i++){
if (nums[i] == arr[i]) {
continue;
}else {
begin = i;
break;
}
}
// 从后往前, 新旧数组对比, 记录结束值
for (int i = nums.length - 1; i >= 0; i--){
if (nums[i] == arr[i]){
continue;
}else {
end = i;
break;
}
}
// 如果begin等于end, 则表示原来的数组已排序 返回0
int res = end - begin == 0 ? 0 : end - begin + 1;
// System.out.println(res);
return res;
}
}
public class Test {
public static void main(String[] args) {
new Solution().findUnsortedSubarray( new int[]{2,6,4,8,10,9,15}); // 输出:5
new Solution().findUnsortedSubarray( new int[]{1,2,3,4}); // 输出:0
new Solution().findUnsortedSubarray( new int[]{1}); // 输出:0
}
}
【代码】排序
package com.company;
import java.util.*;
// 2022-02-13
class Solution {
public int findUnsortedSubarray(int[] nums) {
if (isSorted(nums)){
return 0;
}
int[] arr = new int[nums.length];
System.arraycopy(nums, 0, arr, 0, nums.length);
// 这里排序, 因为第一步已经判断是否是有序数组, 所以不存在越界的问题
Arrays.sort(nums);
int left = 0;
while (nums[left] == arr[left]){
left++;
}
int right = nums.length - 1;
while (nums[right] == arr[right]){
right--;
}
// System.out.println(right - left + 1);
return right - left + 1;
}
private boolean isSorted(int[] nums) {
for (int i = 1; i < nums.length; i++){
if (nums[i] < nums[i - 1]){
return false;
}
}
return true;
}
}
public class Test {
public static void main(String[] args) {
new Solution().findUnsortedSubarray( new int[]{2,6,4,8,10,9,15}); // 输出:5
new Solution().findUnsortedSubarray( new int[]{1,2,3,4}); // 输出:0
new Solution().findUnsortedSubarray( new int[]{1}); // 输出:0
}
}
扩展:leecode看到另一个比较好的几个分析
变形题
【代码】admin
package com.company;
import java.util.*;
// 2022-02-13
class Solution {
public List<Integer> findUnsortedSubarray2(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int i = 1; i < nums.length; i++){
if (check(nums, i)){
list.add(i);
}
}
System.out.println(list);
}
// 分2步来: 左边小于 右边大于
private boolean check(int[] nums, int index) {
// 左边小于
for (int i = 0; i < index; i++){
if (nums[i] > nums[index]){
return false;
}
}
// 右边大于
for (int i = index + 1; i < nums.length; i++){
if (nums[index] > nums[i]){
return false;
}
}
return true;
}
}
public class Test {
public static void main(String[] args) {
new Solution().findUnsortedSubarray2(new int[] {2,3,1,8,9,20,12}); // 输出:3,4
}
}
【代码】儒雅随荷0
class Solution {标签:nums,int,Solution,581,length,最短,LeeCode,new,public From: https://blog.51cto.com/u_13682316/6054570
public int[] findUnsortedSubarray(int[] nums) {
int[] temp = new int[nums.length];
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
} else {
temp[i] = -1;
}
if (nums[nums.length - i - 1] < min) {
min = nums[nums.length - i - 1];
} else {
temp[nums.length - i - 1] = -1;
}
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (temp[i] != -1) {
list.add(i);
}
}
int[] ans = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
ans[i] = list.get(i);
System.out.println(ans[i]);
}
return ans;
}
public static void main(String[] args) {
Solution solution = new Solution();
solution.findUnsortedSubarray(new int[] {2,3,1,8,9,20,12});
}
}
作者:儒雅随荷0
链接:https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/920723/bian-xing-ti-zi-jie-mian-shi-by-chenjial-s4gi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。