uopspop

Untitled

Jul 26th, 2021
948
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public int findMin(int[] nums) {
  3.         if (nums.length == 1) return nums[0]; // [1]
  4.        
  5.         // n <= 5000 = 5 * 10^3 --> O(n^2)
  6.        
  7.         int i_left = 0;
  8.         int i_right = nums.length - 1;
  9.        
  10.         while (true) {
  11.             if (i_left > i_right) break;
  12.            
  13.             int i_mid = (i_left + i_right) / 2;
  14.            
  15.             // find the gap
  16.             int i_mid_next = (i_mid + 1) % nums.length;
  17.             if (nums[i_mid] > nums[i_mid_next]) {
  18.                 // found the gap
  19.                 return nums[i_mid_next]; // return the smallest number
  20.             }
  21.            
  22.             int i_mid_prev = ((i_mid - 1) + nums.length) % nums.length;
  23.             if (nums[i_mid_prev] > nums[i_mid]) {
  24.                 // found the gap
  25.                 return nums[i_mid];
  26.             }
  27.            
  28.             if (nums[i_mid] > nums[i_left]) {
  29.                 // going up trend - the gap is at the right side
  30.                 i_left = i_mid + 1;
  31.             }else if (nums[i_mid] < nums[i_left]) {
  32.                 // going down trend - the gap is at the left side
  33.                 i_right = i_mid - 1;
  34.             }else if (nums[i_mid] == nums[i_left]) {
  35.                 // this is like going up trend, too
  36.                 i_left = i_mid + 1; // attention: be sure to cover all cases
  37.             }
  38.            
  39.         }
  40.        
  41.         return -999; // should not reach here
  42.        
  43.     }
  44. }
RAW Paste Data