You are given an array (zero indexed) of N non-negative integers, A0, A1 ,…, AN-1. Find the minimum sub array Al, Al+1 ,…, Ar so if we sort(in ascending order) that sub array, then the whole array should get sorted. If A is already sorted, output -1.
public class Solution { public ArrayList<Integer> subUnsort(ArrayList<Integer> A) { ArrayList<Integer> sorted = new ArrayList<>(A); Collections.sort(A); int left = -1; int right = -1; for (int i = 0; i < A.size(); i ++) { int curr = sorted.get(i); int orig = A.get(i); if (curr != orig) { left = i; break; } } for (int i = A.size() - 1; i >= 0; i --) { int curr = sorted.get(i); int orig = A.get(i); if (curr != orig) { right = i; break; } } ArrayList<Integer> result = new ArrayList<>(); if (left != -1 && right != -1) { result.add(left); result.add(right); } else { result.add(-1); } return result; } }
思路2
1 2 3 3 4 5 - sorted A = [1, 3, 2, 3 4, 5] min 1 2 2 3 4 5 max 1 3 3 3 4 5
public class Solution { public ArrayList<Integer> subUnsort(ArrayList<Integer> A) { int n = A.size(); int[] mins = new int[n]; int[] maxs = new int[n]; maxs[0] = A.get(0); for(int i = 1; i < n; i++) { maxs[i] = Math.max(A.get(i), maxs[i-1]); } mins[n-1] = A.get(n-1); for(int i = n - 2; i >= 0; i--) { mins[i] = Math.min(A.get(i), mins[i+1]); } ArrayList<Integer> result = new ArrayList<Integer>(); int start = 0; while (start < n && mins[start] == A.get(start)) start++; int end = n - 1; while (end >= 0 && maxs[end] == A.get(end)) end--; if(start == n) result.add(new Integer(-1)); else { result.add(new Integer(start)); result.add(new Integer(end)); } return result; } }