0、tips

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的
  • 数组的元素是不能删的，只能覆盖。

总结：

学习时长：三小时。今天的题都是比较基础的，直接运用算法框架就能写，977有序数组题没看仔细平方卡了一下。前面花时间右总结了一下二分法的框架和细节。

1、704二分查找

labuladong文章链接
代码随想录文章链接
视频链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

  • 拿到这道排序题，首先看到是对有序数组查找一个数，可以使用二分查找，复杂度OlogN。对于二分查找有三种类型：查找一个数、查找左侧边界、查找右侧边界，每一种都可以用左闭右闭和左闭右开的方法去索引。

这里我掌握左闭右闭的二分框架。

  • 思路：
    • 首先明确我使用左闭右闭的框架，即左右双指针都是即将搜索的区间边界。得到初始条件int left = 0, right = nums.size()-1
    • 然后明确循环条件，搜索有效的条件应该是左右边界重合。得到left <= right
    • 最后保证每次循环更新的左右双指针都左闭右闭
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;   
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

在框架中mid = left + (right - left) / 2和(right + left)/2结果相同，但是可以有效防止left和right太大，直接相加导致溢出的情况。

左闭右开：

  • 思路：
    • 首先明确使用左闭右开的框架，即左指针是即将搜索的左区间边界，右指针是即将搜索的右区间边界+1。得到初始条件int left = 0, right = nums.size()
    • 然后明确循环条件，搜索有效的条件应该是左右边界重合。由于右指针是开区间，它的前一个才是右边界。得到left < right
    • 最后保证每次循环更新的左右双指针都左闭右开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(vector<int>& nums, int target) {
    int left = 0,right = nums.size();
    while(left < right){
        int mid = left + (right-left)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid] < target){
            left = mid+1;
        }else if(nums[mid] > target){
            right = mid;
        }
    }
    return -1;
}

2、27移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
思路：快慢双指针解法，复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
int removeElement(vector<int>& nums, int val) {
    int low = 0, fast = 0;
    while(fast<nums.size()){
        if(nums[fast]!=val){
            nums[low] = nums[fast];
            low++;
        }
        fast++;
    }
    return low;
}

3、977有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按非递减顺序排序。

首先拿到这一题，最先想到的是先平方，再排序，鉴于不怎么会排序算法就没继续深入想，用stl的排序这题就做的没啥水平了。
然后想到这个整数数组平方之后最大的数一定出现在左右两端，没有负数也就只有在右边。由于题目要求升序，那就要最大放右边，那可能我还要把最右边那个数交换到其他位置上，越来越复杂了，原因在于我受上一题影响以为要在原数组上改，其实题目要返回新数组，题目没看清。

思路：左右双指针，复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> sortedSquares(vector<int>& nums) {
    vector<int> re(nums.size());
    int end = nums.size()-1;
    int left = 0,right = nums.size()-1;

    while(left<=right){
        int lv = nums[left]*nums[left];
        int rv = nums[right]*nums[right];
        if(lv > rv){
            re[end--] = lv;
            left++;
        }else{
            re[end--] = rv;
            right--;
        }
    }
    return re;
}