fd

dingjikerbo · dingjikerbo · commit 8aa06748e8d5 · 2017-12-09T16:18:07.000+08:00
diff --git a/solution/src/main/java/com/inuker/solution/FindMinimumInRotatedSortedArray.java b/solution/src/main/java/com/inuker/solution/FindMinimumInRotatedSortedArray.java
@@ -7,20 +7,19 @@
 public class FindMinimumInRotatedSortedArray {
 
     public int findMin(int[] nums) {
-        for (int left = 0, right = nums.length - 1; left >= 0 && left <= right; ) {
-            if (nums[right] > nums[left]) {
+        int left = 0, right = nums.length - 1;
+        while (left < right) {
+            if (nums[left] < nums[right]) {
                 return nums[left];
             }
-            int mid = left + ((right - left) >> 1);
+            int mid = (left + right) / 2;
 
-            if (nums[mid] > nums[left]) {
+            if (nums[mid] >= nums[left]) {
                 left = mid + 1;
-            } else if (nums[mid] < nums[right]) {
-                right = mid;
             } else {
-                return Math.min(nums[left], nums[right]);
+                right = mid;
             }
         }
-        return 0;
+        return nums[left];
     }
 }
diff --git a/solution/src/main/java/com/inuker/solution/FindMinimumInRotatedSortedArrayII.java b/solution/src/main/java/com/inuker/solution/FindMinimumInRotatedSortedArrayII.java
@@ -9,10 +9,10 @@ public class FindMinimumInRotatedSortedArrayII {
     public int findMin(int[] nums) {
         int left = 0, right = nums.length - 1;
 
-        for ( ; left < right; ) {
-            int mid = left + ((right - left) >> 1);
+        while (left < right) {
+            int mid = (left + right) / 2;
 
-            if (nums[right] > nums[left]) {
+            if (nums[left] < nums[right]) {
                 return nums[left];
             }
 
@@ -21,6 +21,12 @@ public int findMin(int[] nums) {
             } else if (nums[mid] < nums[right]) {
                 right = mid;
             } else {
+                /**
+                 * 这里表示mid不在左单调区间，也不在右单调区间，有两种情况
+                 * 1，nums[mid] == nums[left]，此时最小值肯定在left右边，有可能在mid左边，也可能在mid右边
+                 * 2，nums[mid] == nums[right]，此时最小值肯定在left右边，但可能在mid右边，也可能在mid左边
+                 * 综上，肯定在left右边
+                 */
                 left++;
             }
         }

Original file line number	Diff line number	Diff line change
`@@ -7,20 +7,19 @@`
`7`	`7`	`public class FindMinimumInRotatedSortedArray {`
`8`	`8`
`9`	`9`	`public int findMin(int[] nums) {`
`10`		`- for (int left = 0, right = nums.length - 1; left >= 0 && left <= right; ) {`
`11`		`- if (nums[right] > nums[left]) {`
	`10`	`+ int left = 0, right = nums.length - 1;`
	`11`	`+ while (left < right) {`
	`12`	`+ if (nums[left] < nums[right]) {`
`12`	`13`	`return nums[left];`
`13`	`14`	`}`
`14`		`- int mid = left + ((right - left) >> 1);`
	`15`	`+ int mid = (left + right) / 2;`
`15`	`16`
`16`		`- if (nums[mid] > nums[left]) {`
	`17`	`+ if (nums[mid] >= nums[left]) {`
`17`	`18`	`left = mid + 1;`
`18`		`- } else if (nums[mid] < nums[right]) {`
`19`		`- right = mid;`
`20`	`19`	`} else {`
`21`		`- return Math.min(nums[left], nums[right]);`
	`20`	`+ right = mid;`
`22`	`21`	`}`
`23`	`22`	`}`
`24`		`- return 0;`
	`23`	`+ return nums[left];`
`25`	`24`	`}`
`26`	`25`	`}`