33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II && 153. Find Minimum in Rotated Sorted Array && 154. Find Minimum in Rotated Sorted Array II
33. Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
public class Solution { public int search(int[] nums, int target) { int len = nums.length; int leftMin = nums[0]; int rightMax = nums[len - 1]; if (target > rightMax && target < leftMin) return -1; boolean targetAtLeft = target >= leftMin; int left = 0; int right = len - 1; while (left <= right) { int mid = (left + right) / 2; int midVal = nums[mid]; if (midVal == target) return mid; if (targetAtLeft) { if (midVal >= leftMin && midVal < target) left = mid + 1; // go right else right = mid - 1; //go left } else { if (midVal <= rightMax && midVal > target) right = mid - 1; // go left else left = mid + 1; //go right } } return -1; } }
81. Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What ifduplicatesare allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
public class Solution { public boolean search(int[] nums, int target) { int left = 0; int right = nums.length - 1; int rightMax = nums[right]; if(nums[left] == target) return true; //Do this while loop to convert it back to problem 33. while(nums[left] == rightMax) { ++left; if(left>right) return false; } int leftMin = nums[left]; if (target > rightMax && target < leftMin) return false; boolean targetAtLeft = target >= leftMin; while (left <= right) { int mid = (left + right) / 2; int midVal = nums[mid]; if (midVal == target) return true; if (targetAtLeft) { if (midVal >= leftMin && midVal < target) left = mid + 1; // go right else right = mid - 1; //go left } else { if (midVal <= rightMax && midVal > target) right = mid - 1; // go left else left = mid + 1; //go right } } return false; } }
153. Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
public class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } return nums[left]; } }
154. Find Minimum in Rotated Sorted Array II
Follow upfor "Find Minimum in Rotated Sorted Array":
What ifduplicatesare allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
public class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else if (nums[mid] < nums[right]) right = mid; else --right; } return nums[left]; } }优质内容筛选与推荐>>
1、Python百度音乐小爬虫
2、opencv中RGB转HSV
3、MySQL 5.1参考手册
4、盒子模型布局
5、20165104孟凡斌-第一次Java考试课下作业