34. Find First and Last Position of Element in Sorted Array
Дан массив целых чисел nums, отсортированный в неубывающем порядке, найдите начальную и конечную позицию заданного целевого значения.
Если целевое значение не найдено в массиве, верните [-1, -1].
C# решение
сопоставлено/оригиналpublic class Solution {
public int[] SearchRange(int[] nums, int target) {
int firstOccurrence = this.FindBound(nums, target, true);
if (firstOccurrence == -1) {
return new int[] { -1, -1 };
}
int lastOccurrence = this.FindBound(nums, target, false);
return new int[] { firstOccurrence, lastOccurrence };
}
private int FindBound(int[] nums, int target, bool isFirst) {
int N = nums.Length;
int begin = 0, end = N - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums[mid] == target) {
if (isFirst) {
if (mid == begin || nums[mid - 1] != target) {
return mid;
}
end = mid - 1;
} else {
if (mid == end || nums[mid + 1] != target) {
return mid;
}
begin = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
begin = 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 vector<int>& SearchRange(vector<int>& nums, int target) {
int firstOccurrence = this.FindBound(nums, target, true);
if (firstOccurrence == -1) {
return new int[] { -1, -1 };
}
int lastOccurrence = this.FindBound(nums, target, false);
return new int[] { firstOccurrence, lastOccurrence };
}
private int FindBound(vector<int>& nums, int target, bool isFirst) {
int N = nums.size();
int begin = 0, end = N - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums[mid] == target) {
if (isFirst) {
if (mid == begin || nums[mid - 1] != target) {
return mid;
}
end = mid - 1;
} else {
if (mid == end || nums[mid + 1] != target) {
return mid;
}
begin = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
return -1;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int[] searchRange(int[] nums, int target) {
int firstOccurrence = this.findBound(nums, target, true);
if (firstOccurrence == -1) {
return new int[] { -1, -1 };
}
int lastOccurrence = this.findBound(nums, target, false);
return new int[] { firstOccurrence, lastOccurrence };
}
private int findBound(int[] nums, int target, boolean isFirst) {
int N = nums.length;
int begin = 0, end = N - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums[mid] == target) {
if (isFirst) {
if (mid == begin || nums[mid - 1] != target) {
return mid;
}
end = mid - 1;
} else {
if (mid == end || nums[mid + 1] != target) {
return mid;
}
begin = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
return -1;
}
}JavaScript решение
сопоставлено/оригиналvar searchRange = function(nums, target) {
const findFirst = () => {
let left = 0, right = nums.length - 1, idx = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
idx = mid;
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return idx;
};
const findLast = () => {
let left = 0, right = nums.length - 1, idx = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
idx = mid;
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return idx;
};
return [findFirst(), findLast()];
};Python решение
сопоставлено/оригиналclass Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
lower_bound = self.findBound(nums, target, True)
if lower_bound == -1:
return [-1, -1]
upper_bound = self.findBound(nums, target, False)
return [lower_bound, upper_bound]
def findBound(self, nums: List[int], target: int, isFirst: bool) -> int:
N = len(nums)
begin, end = 0, N - 1
while begin <= end:
mid = int((begin + end) / 2)
if nums[mid] == target:
if isFirst:
if mid == begin or nums[mid - 1] < target:
return mid
end = mid - 1
else:
if mid == end or nums[mid + 1] > target:
return mid
begin = mid + 1
elif nums[mid] > target:
end = mid - 1
else:
begin = mid + 1
return -1Go решение
сопоставлено/оригиналfunc searchRange(nums []int, target int) []int {
firstOccurrence := findBound(nums, target, true)
if firstOccurrence == -1 {
return []int{-1, -1}
}
lastOccurrence := findBound(nums, target, false)
return []int{firstOccurrence, lastOccurrence}
}
func findBound(nums []int, target int, isFirst bool) int {
N := len(nums)
begin, end := 0, N-1
for begin <= end {
mid := (begin + end) / 2
if nums[mid] == target {
if isFirst {
if mid == begin || nums[mid-1] != target {
return mid
}
end = mid - 1
} else {
if mid == end || nums[mid+1] != target {
return mid
}
begin = mid + 1
}
} else if nums[mid] > target {
end = mid - 1
} else {
begin = mid + 1
}
}
return -1
}Algorithm
Пример:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
👨💻
Алгоритм:
1️⃣
Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.
2️⃣
Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.
3️⃣
Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.