数组part01-代码随想录day 1网站首页 技术教程

数组part01-代码随想录day 1

Sakura7301 2024-06-14 17:18:54

简介数组part01-代码随想录day 1

1.二分查找

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

示例 1:

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

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

就像题目，这道题考察二分法，怎么办呢？
准备三个变量，left, mid, right
乍一看，我们要找的数组肯定不能小于left，且不能大于right，否则他就不属于这个区间，因为我们是自增数组，但left和right是可以相等的。相等时left/mid/right指向同一个元素，所以，我们的循环条件就有了==> left <= right
mid始终取[left, right]区间的中间值((right - left)/2 + left)
每次循环，比较mid下标的值与tar是否相等
1. 相等，记录mid，返回
2. 不相等，再次判断大小
  1. target大于mid，很明显，实际的数据大概在(mid，right]这个区间(左开右闭)，所以我们让left=mid + 1；
  2. target小于mid，很明显，实际的数据大概在[left, mid)这个区间(左闭右开)，所以我们让right=mid - 1；
  3. 每次循环都需要更新mid((right - left)/2 + left)。
准备的差不多了，此时还需要再考虑一下，如果已经不在我们的[left, right]区间了，应当返回-1。

题解：

int search(int* nums, int numsSize, int target){
    unsigned int ret = -1;
    unsigned int left = 0;
    unsigned int right = numsSize - 1;
    unsigned int mid = (right - left)/2 + left;
    while(left <= right){
        if(nums[left] > target || nums[right] < target){
            break;
        }
        
        if(nums[mid] == target){
            ret = mid;
            break;
        } else {
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
            mid = (right - left)/2 + left;
        }
    }

    return ret;
}

我发现很多人的题解都使用了多个return语句，但就代码的安全性而言，使用多个return并不是一个好的习惯。函数内应当只有一个返回点。

因此我觉得不应当过分追求速度，而忽略了编码规范。

2.移除元素

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：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]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

这道题乍一看很简单嘛，但是重点来了—> 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
嘶~暴力法貌似不好使啊，那怎么办，要不双指针换位置试下？
首先我们准备两个指针，left和right，让他们都指向第一个元素。
然后呢，我们记住一点，right去寻找目标元素，left来指向需要换位置的元素。
循环条件就不必多说了，遍历所有元素。
每次循环呢，我们都去比较一下right和val的值：
1. 相等！我们需要移除对吧，所以我们让right指针右移动，去看看下一个元素。同时呢，更新一下要返回的数组大小。
2. 不相等！刚刚说过了“right去寻找目标元素，left来指向需要换位置的元素。”所以呢，我们交换一下left和right指向的元素，ok换完位置了，此时left指向的已经是正常元素了，而right指向的是需要移除的元素，所以我们两个指针都需要右移。

题解：

int removeElement(int* nums, int numsSize, int val){
    /* ret初始值为数组原始大小 */
    unsigned int ret = numsSize;
    /* 初始化left和right */
    unsigned int left = 0;
    unsigned int right = 0;
    /* 准备临时变量 */
    int temp = 0;
    for(int i = 0; i < numsSize; i++){
        /* 找到目标数值，需要删除 */
        if(nums[right] == val){
            /* right指针右移 */
            right ++;
            /* 更新要返回的数组大小 */
            ret --;
        } else {
            /* 没找到目标数值，交换left和right下标的值 */
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            /* left和right均右移一位 */
            left ++;
            right ++;
        }
    }
    return ret;
}