Start from left, increase pointer until the element is no longer ascending, then do binary search, find the left boundary, continue move the pointers until meeting another element which is smaller, then do binary search to update the left boundary. Do the same for right boundary.
The key to this solution is do the binary search correctly, watching out the boundary case. Since we are not looking for number but the closest number in the list, so we need to 1) exit the while() loop when there are only two elements left in the search window, 2) include the middle number in the search window.
static int[] findMinUnsortedWindow2(int[] nums){
int p=0, len = nums.length, left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
while(p<len){
while(p+1<len && nums[p+1]>=nums[p]){p++;}
if(p+1<len)//we found the number broke the order, do binary search
left = Math.min(left, binarySearch3(nums, 0, Math.min(p, left), nums[p+1]));p++;
}
//use -1, -1 to indicate the array is sorted already
if(left == Integer.MAX_VALUE)return new int[]{-1, -1};
while(p>=0){
while(p-1>=0 && nums[p-1]<=nums[p]){p--;}
if(p-1>=0)
right = Math.max(right, binarySearch4(nums, Math.max(p, right), len-1, nums[p-1]));
p--;
}
//find the minimum index i which nums[i] bigger than k in sorted array
static int binarySearch3(int[] nums, int p0, int p1, int k){while(p0<p1-1){//binary search window size is larger than 2 elements
int mid = (p0+p1)/2;
if(nums[mid]>k)
p1 = mid;//including the middle in search window
else
p0 = mid;}
return nums[p0]>k?p0:p1;
}
//find the maximum index i which nums[i] smaller than k in sorted array
static int binarySearch4(int[] nums, int p0, int p1, int k){while(p0<p1-1){
int mid = (p0+p1)/2;
if(nums[mid]<k)
p0 = mid;
else
p1 = mid;
}
return nums[p1]<k?p1:p0;
}
I tried a nums[]={1,2,5,3,4,7,5,6,8,10}; it seems it goes to infinite loop. Besides, can your code pass this case? {1,2,3,4,5,6,7,4,3,6,5,6,7,8,9}, the left bound is 7, and right bound is 6, but 7 is larger than 6.
ReplyDeletei quickly write the code to demonstrate the binary search idea. , there is bug in the while look, e.g. while(p+1=nums[p]){p++;},
ReplyDeletealso the resulting right bound is off 1 position.
for {1,2,3,4,5,6,7,4,3,6,5,6,7,8,9},
when the while loop will break at index 7, 8,10, then we do binary search for 4 in (0, 6), will set left bound to 4, and for 3 in (0,4) will set left bound of 3
anyway, the best solution is the min/max stack solution in this link: http://blueocean-penn.blogspot.com/2015/01/given-unsorted-list-find-minimum-window.html.
ReplyDeletenote i actually use array to keep track of min/max indices.
I rewrote the codes, it passed the following test cases: 2, 3, 4, 6, 4, 3, 2, 7, 8, 9 and 7,8,9,2,3,2,3,4. The key is to do binary search correctly, be careful with the "equal" case.
ReplyDelete