编程知识 cdmana.com

Yyds dry goods counting leetcode algorithm problem: search rotation sorting array

subject :

An array of integers nums In ascending order , The values in the array Different from each other .

Before passing it to a function ,nums In some unknown subscript k(0 <= k < nums.length) On the rotate , Make array [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]( Subscript from 0 Start Count ). for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into  [4,5,6,7,0,1,2] .

Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to  -1 .

You have to design a time complexity of O(log n) The algorithm to solve this problem .

 

Example 1:

Input :nums = [4,5,6,7,0,1,2], target = 0

Output :4

Example  2:

Input :nums = [4,5,6,7,0,1,2], target = 3

Output :-1

Example 3:

Input :nums = [1], target = 0

Output :-1

Code implementation :

      
      
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/174/202206231833089475.html

Scroll to Top