0%

LeetCode - 34 - 在排序数组中查找元素的第一个和最后一个位置

题目

34. 在排序数组中查找元素的第一个和最后一个位置

题解

Leetcode 手册

官方题解

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 34. 在排序数组中查找元素的第一个和最后一个位置
// find-first-and-last-position-of-element-in-sorted-array

const binarySearch = (nums, target, lower) => {
let left = 0,
right = nums.length - 1,
ans = nums.length;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
};

var searchRange = function (nums, target) {
let ans = [-1, -1];
const leftIdx = binarySearch(nums, target, true);
const rightIdx = binarySearch(nums, target, false) - 1;
if (
leftIdx <= rightIdx &&
rightIdx < nums.length &&
nums[leftIdx] === target &&
nums[rightIdx] === target
) {
ans = [leftIdx, rightIdx];
}
return ans;
};

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange2 = function (nums, target) {
debugger;
function search(target) {
let left = 0,
right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
const l = search(target);
const r = search(target + 1);
return l == nums.length || l >= r ? [-1, -1] : [l, r - 1];
};

let nums = [5, 7, 7, 8, 8, 10];
let target = 8;
console.log(searchRange(nums, target));
console.log(searchRange2(nums, target));

收获

碰到代码里面有个 >> 操作符,不明白它的作用,查了一下

8.右移运算符(>>)
定义:将一个数的各二进制位全部右移若干位,正数左补 0,负数左补 1,右边丢弃。
例如:a=a>>2 将 a 的二进制位右移 2 位,左补 0 或者 左补 1 得看被移数是正还是负。
操作数每右移一位,相当于该数除以 2。

也就是说

1
2
3
8 >> 1 = 4
8 >> 2 = 2
8 >> 3 = 0