广州建设厅网站,西宁网站seo外包,深圳专业画册设计机构,万能浏览器手机版下载附上我的github仓库#xff0c;会不断更新leetcode解题答案#xff0c;提供一个思路#xff0c;大家共勉 在我的主页和github上可以看到更多的关于leetcode的解题报告#xff01;#xff08;因为不知道为什么掘金没有将其发布出来#xff0c;目前已经联系掘金客服#x…附上我的github仓库会不断更新leetcode解题答案提供一个思路大家共勉 在我的主页和github上可以看到更多的关于leetcode的解题报告因为不知道为什么掘金没有将其发布出来目前已经联系掘金客服 希望可以给star鼓励继续更新解题思路 author: thomas No34Search for Range(Medium) 题目 Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithms runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4]. // 下标34是数组8
复制代码这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置,没如果没有找到就返回[-1,-1] 思路 这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置而且限定了时间复杂度为O(logn)这是典型的二分查找法的时间复杂度所以这道题我们也需要用此方法。 方法一 我们的思路是对原数组使用两次二分查找法分别找出一个起始和结束位置方法二利用二分法找到起始位置然后向右遍历找到边界代码 方法一let arr1 [1,1,2,2,3,4,4,7,8];
let arr [5,7,7,8,8,10],target 8;
let searchRange function(arr, target) {let len arr.length,res [-1, -1];for (let i 0, j len-1; i j;) {let mid Math.floor((i j) / 2);if (arr[mid] target) { // 先判断小于target的情况i mid 1;}else {j mid - 1; // 应对刚好i mid 1后就指向了target值if (arr[mid] target) {res[0] mid; // 得到起始index}}}for (let i 0, j len-1; i j;) {let mid Math.floor((i j) / 2);if (arr[mid] target) {// 先判断大于target的情况j mid - 1;}else {i mid 1; // 应对刚好i mid 1后就指向了target值if (arr[mid] target) {res[1] mid; // 得到结束index}}}return res;
};
console.log(searchRange(arr,target)); // [3, 4]
复制代码方法二/*** 方法2** 找到res[0]之后就向右遍历直到不是该值就可以得到右边界了* 时间复杂度没上面的方法好*/let searchRange1 function(arr, target) {let len arr.length,res [-1, -1];for (let i 0, j len-1; i j;) {let mid Math.floor((i j) / 2);if (arr[mid] target) {i mid 1;}else {j mid - 1; // 应对刚好i mid 1后就指向了target值if (arr[mid] target) {res[0] mid; // 得到最左边的值}}}let k;res[1] res[0];for (k res[0] 1; k len; k) { // 找到右边界if (arr[k] target) {res[1] 1;}}return res;
};
console.log(searchRange1([1],1)); // [0, 0]
console.log(searchRange1([2,2],2)); // [0, 1]
console.log(searchRange1([5,7,7,8,8,10],8)); // [3, 4]
console.log(searchRange1([1,3],1)); // [0, 0]
console.log(searchRange1([3,3,3],3)); // [0, 0]
复制代码 注二分法其假设我们找到目标值但是有多个目标值连在一起 1、如果我们先判断arr[mid] target(先判断小于target的情况),再判断剩下的,最后得到的结果就是要找的多个目标值target的最左边的值2、如果我们先判断arr[mid] target(也就是先判断大于target的情况),再判断剩下的,最后得到的结果就是要找的多个目标值target的最右边的值 No35Search Insert Position(Easy) 题目 从给定排好顺序的数组找出给定目标数字下标存在则返回下标不存在则返回目标数应该插入的位置下标。 Example 1: Input: [1,3,5,6], 5
Output: 2
复制代码Example 2: Input: [1,3,5,6], 2
Output: 1
复制代码Example 3: Input: [1,3,5,6], 7
Output: 4
复制代码Example 4: Input: [1,3,5,6], 0
Output: 0
复制代码思路 思路就是每次取中间如果等于目标即返回否则根据大小关系切去一半。因此算法复杂度是O(logn)空间复杂度O(1) 代码 let arr [1,3,5,6],target 5;let searchInset function(arr, target) {let len arr.length,res 0;for (let i 0, j len -1; i j;) {let mid Math.floor((ij)/2);if (arr[mid] target) {return mid;}if (arr[mid] target) {i mid 1;res mid1; // 更新res}else {j mid - 1;}}return res; //
}
console.log(searchInset(arr,target)); // 2
console.log(searchInset([1,3,5,6],2)); // 2
复制代码 注意:二分法有一个好处:就是当循环结束时: (1)如果找到目标元素那么就返回当前位置 (2)如果没有找到目标元素那么i一定停在恰好比目标大的index上j一定停在恰好比目标小的index上所以个人比较推荐这种实现方式。(初始i在左j在右)
