本文共 2946 字,大约阅读时间需要 9 分钟。
找旋转数组中的target
解法一:
public class Solution { public int search(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int beg = 0; int end = nums.length - 1; while (beg < end) { int mid = beg + (end - beg) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] >= nums[beg]) { if (nums[mid] > target && target >= nums[beg]) { end = mid - 1; } else { beg = mid + 1; } } else { if (nums[mid] < target && nums[end] >= target) { beg = mid + 1; } else { end = mid - 1; } } } return nums[beg] == target ? beg : -1; }}
解法二:
找到最小值位置,然后二分查找target的时候,将mid重映射到未旋转前数组的位置
其中找最小值先找到旋转前前半个递增的子数组,所以是无脑 nums[mid] > nums[end] -- beg = mid + 1;
public class Solution { public int search(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int beg = 0; int end = nums.length - 1; while (beg < end) { int mid = beg + (end - beg) / 2; if (nums[mid] > nums[end]) { beg = mid + 1; } else { end = mid; } } int rot = beg; beg = 0; end = nums.length - 1; while (beg <= end) { int mid = beg + (end - beg) / 2; int realMid = (mid + rot) % nums.length; if (nums[realMid] == target) { return realMid; } else if (nums[realMid] > target) { end = mid - 1; } else { beg = mid + 1; } } return -1; }}
假如数组中存在重复数字呢?
public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int beg = 0; int end = nums.length - 1; while (beg < end) { int mid = beg + (end - beg) / 2; if (nums[mid] == target) { return true; } if (nums[mid] > nums[beg]) { if (nums[mid] > target && target >= nums[beg]) { end = mid - 1; } else { beg = mid + 1; } } else if (nums[mid] < nums[beg]) { if (nums[mid] < target && nums[end] >= target) { beg = mid + 1; } else { end = mid - 1; } } else { beg++; } } return nums[beg] == target; }}
转载地址:http://svhld.baihongyu.com/