33. Search in Rotated Sorted Array
Есть массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями).
Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2].
Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве.
C# решение
сопоставлено/оригиналpublic class Solution {
public int Search(int[] nums, int target) {
int n = nums.Length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[n - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int answer = BinarySearch(nums, 0, left - 1, target);
if (answer != -1) {
return answer;
}
return BinarySearch(nums, left, n - 1, target);
}
private int BinarySearch(int[] nums, int left_boundary, int right_boundary, int target) {
int left = left_boundary, right = right_boundary;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int Search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[n - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int answer = BinarySearch(nums, 0, left - 1, target);
if (answer != -1) {
return answer;
}
return BinarySearch(nums, left, n - 1, target);
}
private int BinarySearch(vector<int>& nums, int left_boundary, int right_boundary, int target) {
int left = left_boundary, right = right_boundary;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}Java решение
сопоставлено/оригиналpublic class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[n - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int answer = binarySearch(nums, 0, left - 1, target);
if (answer != -1) {
return answer;
}
return binarySearch(nums, left, n - 1, target);
}
private int binarySearch(int[] nums, int leftBoundary, int rightBoundary, int target) {
int left = leftBoundary, right = rightBoundary;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}JavaScript решение
сопоставлено/оригинал/** * @param {number[]} nums
* @param {number} target * @return {number}
*/var search = function(nums, target) {
let res=nums.indexOf(target);
if(res){ return res;
} else if(res==-1)
{ return -1;
} else{
return res; }
};Python решение
сопоставлено/оригиналclass Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > nums[-1]:
left = mid + 1
else:
right = mid - 1
def binarySearch(left_boundary, right_boundary, target):
left, right = left_boundary, right_boundary
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
if (answer := binarySearch(0, left - 1, target)) != -1:
return answer
return binarySearch(left, n - 1, target)Go решение
сопоставлено/оригиналfunc search(nums []int, target int) int {
n := len(nums)
left, right := 0, n-1
for left <= right {
mid := (left + right) / 2
if nums[mid] > nums[n-1] {
left = mid + 1
} else {
right = mid - 1
}
}
binarySearch := func(left_boundary int, right_boundary int, target int) int {
left, right := left_boundary, right_boundary
for left <= right {
mid := (left + right) / 2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return -1
}
if answer := binarySearch(0, left-1, target); answer != -1 {
return answer
}
return binarySearch(left, n-1, target)
}Algorithm
Пример:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
👨💻
Алгоритм:
1️⃣
Выполните двоичный поиск для определения индекса поворота, инициализируя границы области поиска значениями left = 0 и right = n - 1. Пока left < right:
Пусть mid = left + (right - left) // 2.
Если nums[mid] > nums[n - 1], это предполагает, что точка поворота находится справа от mid, следовательно, мы устанавливаем left = mid + 1. В противном случае, поворот может находиться на позиции mid или левее от mid, в этом случае мы должны установить right = mid.
2️⃣
По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left.
nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1].
3️⃣
Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс.
В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.