代码随想录算法训练营第一天 |-数组篇704&27

数组704-二分查找

梦开始的地方。day1——2023/4/19

题目&难度

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
1
2
3
4
5

难度：简单题。

示例

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3

算法——二分查找法

写在前面——二分查找法的定义：

使用的前提条件：（交集）

1.有序数组

2.数组元素无重复

循环不变量

所谓循环不变量也就是这里的区间定义，闭区间[left,right]和左闭右开区间[left,right)。

二分法：

设定左右指针left，right，每次取查找的中点为mid；

比较nums[mid]和target的大小，若相等则mid就是所需的返回下标。

若nums[mid]>target，此时right=mid，继续判定。

若nums[mid]<target，此时left=mid，继续判定。

嘿，你以为这样就完了？那可不行，好好区分一下，先别想着交差。

1.左闭右闭的情况下，简单来说就是：
$$\begin{gathered} nums[mid]==target,返回mid \\ nums[mid]>target,则right=mid-1,继续判定 \\ nums[mid]<target,则left=mid+1，继续判定 \end{gathered}$$
2.左闭右开的情况：

$$\begin{gathered} nums[mid]==target,返回mid \\ nums[mid]>target,则right=mid,继续判定 \\ nums[mid]<target,则left=mid+1，继续判定 \end{gathered}$$

中间那一句就是区别，this is 街舞。写不对就玩球力。

两种写法

1.左闭右闭left<=right

int search(int *nums, int numsSize, int target){
    //先定义左右指针
    int left = 0;
    int right = numsSize - 1;
    int mid;
    
    //二分法
    while(left <= right){
        //中点，防止溢出处理
        mid = left + (right - left) / 2;
        //开始判定
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    //找不到就返回-1
    return -1; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

好的，信心满满的执行代码，快乐提交。

接下来尝试一下左闭右开的写法。

2.左闭右开left<right

int search(int *nums, int numsSize, int target){
    //先定义左右指针
    int left = 0;
    int right = numsSize; //看到了吗，这里不是-1啦
    int mid ;

    //二分法
    while(left < right){//注意边界条件
        //中点，防止溢出处理
        mid = left + (right - left) / 2;
        //开始判定
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            right = mid;//由于是右开，所以必须取mid
        else
            left = mid + 1;
    }
    //找不到就返回-1
    return -1; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

提交后的数据居然不如左闭右闭，好吧，卡哥说不用在意，那就不去在意！

疑难点分析

为啥mid = (left + right) / 2就会溢出呢，我查阅了资料后整理如下。

梭梭~我们来看一下代码——

int 为4个字节，那么取值范围为- 2147483648~2147483647，这里我取left=2100000000试试看。

#include<stdio.h>

int main(){
	int left = 2100000000;
	int right = 2100000002;

	int mid1 = (left + right) / 2;
	int mid2 = left + (right - left) / 2;

	printf("这是mid1:%d\n",mid1);
	printf("这是mid2:%d\n",mid2);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果：

芜湖，第一种真的溢出了，我们来分析一下。

原来是当(left + right) / 2中，left+right的值（按照小括号优先原则）超过int的最大值时就会直接溢出，根本等不到/2。

而用left + (right - left) / 2时大数减大数，就避免了溢出，因此输出正常。（突然想到了数值分析哈哈）

算法复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

鱼肝油感觉自己又升华了，开心。朋友说有空学学unity，记下了记下了。

数组27——移除元素

题目&难度

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
    
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
    
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

难度：简单题。

示例

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
1
2
3

算法——暴力&双指针

1.暴力解法

两层for循环嵌套，一层用来遍历目前的数组，另一层用来更新（覆盖）数组。

只能覆盖，不能删除。

以下是代码。

//暴力解法
int removeElement(int *nums, int numsSize, int val){
    //第一层for用来遍历目前的数组
    for(int i = 0; i < numsSize; i++){
        if(nums[i] == val){
            //第二层for用来更新数组
            for(int j = i; j < numsSize - 1; j++){
                //因为检测到nums[i]=val需要删除nums[j],故把nums[j+1]往				//前移动到nums[i]的位置
                nums[j] = nums[j + 1];
            }
            //i位置之后的数组整体前移一位，所以i要-1
            i--;
            numsSize--;
        }
    }return numsSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

执行结果如下：

时间复杂度：O(n^2)这就很危险了，我不禁想到自己毕设的代码，那个矩阵之庞大，目标函数是二次的话这波直接时间翻倍了。

空间复杂度：O(1)

2.双指针法

定义双指针，其中，快指针fast用来指向当前要处理的元素，慢指针指向需要赋值的新数组的下标位置。

需要注意的是：

• 当快指针指向的元素不等于val时，此时该元素就是新数组的元素，将快指针的赋值给慢指针，然后两指针同时右移一位。
• 当快指针指向的元素等于val时，此时该元素不是新数组的元素，快指针不动，慢指针右移一位。
• 此时结束后，数组的长度就是我们慢指针的位置啦。

好的，接下来我们一起来看看代码咋个写捏。_(￣▽￣)*

//双指针法
int removeElement(int *nums, int numsSize, int val){
    //初始化双指针
    int slow = 0;
    int fast =0;
    for(; fast < numsSize; fast++){
        if(nums[fast] != val){
            //更新数组
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

采用双指针后，时间骤降，从O(n^2)降到O(n)，值得好好学习。

时间复杂度：O(n)

空间复杂度：O(1)

好啦，今天的训练营任务完成了，我可以去听听操作系统的课啦，我们明天见~