704. 二分查找
-
解决思路
- 基于数组有序的特性，取其中一个值进行比较，即可淘汰该值左边或右边的元素，缩小搜索的区间
- 使用两指针标记需要遍历的区间，取中间值进行比较，淘汰左边或右边元素，不断移动缩小遍历的区间，即可查到
-
代码
public int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while(l target){ r = mid - 1; // 注意点二 }else if(nums[mid] -
注意点
- 核心注意点：避免漏检元素
- 注意点一：while条件中选择 l
- 注意点二：当选择 l target时，r = mid，服务器托管网不能mid-1。因为r所指向的元素在进入第二次循环时，是不会再与target比较，会导致漏检
- 时间复杂度 O(logN) 。总共需要遍历 log2N次，忽略常数2。
-
扩展
-
当元素可重复时，如何定位到与target相等的最小索引
-
public static int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while(l = target){ // 等于target的时候 右指针继续移动，继续寻找最左边的一个 // 如果已达最左的一个，再循环左指针会移动，最终会大于r，取到最左的 r = mid - 1; }else if(nums[mid]
-
80. 删除有序数组中的重复项 II
-
解决思路
- 使用快慢指针遍历，快指针用于判断是否与上一个元素重复，慢指针用于记录下最终有效的数字
- 快指针判断为不重复，慢指针记下来，同时向前移动一位
-
代码
public int removeDuplicates(int[] nums) { // 只允许元素出现一次的情况 int k = 1; int fast = k; int slow = k; // 注意点一 while(fast -
注意点
- 核心注意点：理清快慢指针分别的作用
- 注意点一：快慢指针的起始位置，k
- 注意点二：判断元素是否超过k个重复，因为数组有序，如果当前元素等于前k个位置的元素，说明超过了
-
同类型题目
- https://leetcode.cn/problems/remove-element/description/
- https://leetcode.cn/problems/move-zeroes/description/
977. 有序数组的平方
-
解决思路
- 非递减顺序。即递增但可以重复
- 使用双向指针，比较两指针指向元素的绝对值，绝对值大的计算平方添加进结果数组
-
代码
public int[] sortedSquares(int[] nums) { int[] 服务器托管网res = new int[nums.length]; int l = 0; int r = nums.length-1; int index = nums.length - 1; while(l Math.abs(nums[r])){ res[index] = (int)Math.pow(nums[l],2); l++; }else{ res[index] = (int)Math.pow(nums[r],2); r--; } index --; } return res; } -
注意点
- 这里空间复杂度为O(1)，不是O(n)，因为空间复杂度是计算非答案占用的空间
-
扩展
-
想再节省空间的话，可以比较两个数的平方后，进行交换，右指针一直往前移即可
-
public int[] SortedSquares(int[] nums) { int left = 0; int right = nums.length-1; int leftR = 0, rightR = 0; while(right >= 0){ leftR = nums[left]*nums[left]; rightR = nums[right]*nums[right]; // 左指针的平方比较大，交换到数组的后面来 if(leftR >= rightR){ nums[left] = nums[right]; nums[right] = leftR; }else{ nums[right] = rightR; } right--; } return nums; }
-
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: #yyds干货盘点# LeetCode程序员面试金典：有序矩阵中第 K 小的元素
题目 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。 你必须找到一个内存复杂度优于 O(n2) 的解决方案。 示例 1： 输入：…
