【LeetCode-面试算法经典-Java实现】【081-Search in Rotated Sorted Array II（搜索旋转的排序数组）】
分类：LeetCode
【081-Search in Rotated Sorted Array II（搜索旋转的排序数组）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array.
题目大意
“在旋转数组中搜索值”的后续，如果数组中的值允许重复写一个程序确定一个给定的值是否在数组中。
解题思路
先找最小的数所在的下标，再根据所要找的数字在哪一个部分进行查找。
代码实现
算法实现类
{(int[] nums, int target) {if (nums != null && nums.length > 0) {// 找最小元素对应的下标int minIndex = findMinIndex(nums);// 整个数组全局有序if (minIndex == 0) {return binarySearch(nums, 0, nums.length – 1, target);}// 有两个局部有序区间, 如 4 5 6 7 8 9 0 1 2 3else {// 恬好和后一个有序区间的最后一个元素相等，返回对应的下标if (nums[nums.length – 1] == target) {return true;}(nums[nums.length – 1] > target) {return binarySearch(nums, minIndex, nums.length – 1, target);}// target可能是前一个有序区间中else {return binarySearch(nums, 0, minIndex – 1, target);}}}return false;}/*** 二分搜索** @param nums 数组* @param start 起始位置* @param end 结束位置* @param target 搜索目标* @return true找到，false没有找到*/(int[] nums, int start, int end, int target) {int mid;while (start <= end) {mid = start + ((end – start) >> 1);if (nums[mid] == target) {return true;} else if (nums[mid] > target) {end = mid – 1;} else {start = mid + 1;}}return false;}(int[] nums) {// 参数校验if (nums == null || nums.length < 1) {throw new IllegalArgumentException();}int lo = 0;int hi = nums.length – 1;int mid = 0;// 可以排除数组全局有序的情况while (nums[lo] >= nums[hi]) {// 如果只有两个元素，返回后一个if (hi – lo == 1) {mid = hi;break;}mid = lo + ((hi – lo) >> 1);if (nums[mid] == nums[lo] && nums[mid] == nums[hi]) {sequenceSearchMinIndex(nums, lo, hi);}// 如果mid在前一个有序数组中if (nums[mid] >= nums[lo]) {lo = mid;}(nums[mid] <= nums[hi]) {hi = mid;}}return mid;}/*** 顺序搜索数组中的最小值的下标，nums是由有序数组按某个轴旋转得来的** @param nums 搜索数组* @param start 开始位置* @param end 结束位置* @return 最小值的下标*/(int[] nums, int start, int end) {for (int i = start; i < end; i++) {if (nums[i] > nums[i + 1]) {return i + 1;}}return start;}}评测结果
点击图片，鼠标不释放，，拖动一段位置，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇【LeetCode-面试算法经典-Java实现】【079-Word Search（单词搜索）】下一篇【LeetCode-面试算法经典-Java实现】【082-Remove Duplicates from Sorted List II（排序链表中删除重复元素II）】
顶2踩0
记忆的屏障，曾经心动的声音已渐渐远去。
