当前位置：首页 > news >正文

算法：数组part01：704. 二分查找 +977.有序数组的平方

news 2025/7/26 9:30:40

算法：数组part01：704. 二分查找 +27. 移除元素+977.有序数组的平方

704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/
文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

思想：

题目要达到O(logn)的时间复杂度，显然遍历数组是做不到了，考虑二分查找
使用二分查找的前提是：数组有序且不重复
二分查找根据给定区间的闭合情况，分为左闭右闭区间算法和左闭右开区间算法

解题

左闭右闭

class Solution {public int search(int[] nums, int target) {//左闭右闭算法int left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)/2;if(target==nums[mid]){//找到return mid;}else if(target<nums[mid]){//左侧right=mid-1;}else{//右侧left=mid+1;}}return -1;}
}

左闭右开

class Solution {public int search(int[] nums, int target) {//左闭右闭算法int left=0;int right=nums.length;while(left<right){int mid=(left+right)/2;if(target==nums[mid]){//找到return mid;}else if(target<nums[mid]){//左侧right=mid;}else{//右侧left=mid;}}return -1;}
}

总结

左闭右闭区间算法和左闭右开区间算法的区别：

左闭右闭在where(left<=right)中加上等号，而左闭右开不加等号-------原因是左右边界能取到相同值比如[1,1]；
左闭右闭取左边或右边的时，让right=mid-1，left=mid+1；左闭右开让right=mid,left=mid，这样可以确保一个开区间
左闭右闭初始right=nums.length-1,左闭右开初始right=nums.length

27. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

思想

要移除所有指定val并让让所有剩余元素挨个排在列表的前面，可以直接用暴力解法O(n²)：即遍历数组找到需要移除的元素之后，将它后面的所有元素全部向前移一格；
优化的解法是用双指针，快指针用于遍历数组，若其指向的这个元素不是val，就给慢指针的位置赋值为这个元素，慢指针从数组下标0开始；

解题

暴力解法

class Solution {public int removeElement(int[] nums, int val) {//暴力解法：//遍历数组:找到val，然后将其后面的所有元素前移一格int size=nums.length;for(int i=0;i<size;i++){if(nums[i]==val){for(int j=i+1;j<size;j++){nums[j-1]=nums[j];}i--;size--;}}return size;}
}//这个是参考答案，要更好理解，上面的是我写的// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};

双指针

解法

class Solution {public int removeElement(int[] nums, int val) {int k=0;for(int i=0;i<nums.length;i++){if(nums[i]!=val){nums[k]=nums[i];k++;}}return k;}
}//这个是参考答案，要更好理解，上面的是我写的
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};

总结

双指针法用于在一个for循环中完成两个嵌套for的操作，用一个快指针去遍历，一个慢指针去指向剔除后的新数组。

977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

思想

在O(n)的时间复杂度下解这道题，同样利用双指针的思想；
最重要的是需要理解：这个场景下的最大值只有可能出现在最左和最右。
因此，可以利用left和right对比，将大者放入新数组的尾部；while(left<=right)就一直遍历，这样问题便迎刃而解了；

解题

class Solution {public int[] sortedSquares(int[] nums) {//平方后的最大元素只有可能在数组的两端int left=0;int right=nums.length-1;//定义一个新数组存放排序结果int[] result=new int[nums.length];int index=nums.length-1;while(left<=right){if(nums[left]*nums[left]<nums[right]*nums[right]){result[index--]=nums[right]*nums[right];right--;}else{result[index--]=nums[left]*nums[left];left++;}}return result;}
}//这个是参考答案，要更好理解，上面的是我写的
class Solution {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = result.length - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {// 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置result[index--] = nums[left] * nums[left];++left;} else {result[index--] = nums[right] * nums[right];--right;}}return result;}
}