算法复健-第八天

Array-Easy-移除元素

题面

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

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

解答过程

本题使用快慢指针，快指针用于遍历数组找出目标数字，慢指针用于保存不是目标数字的元素

代码

int removeElement(vector<int>& nums, int val) {
        int fast = 0 , slow = 0;
        for ( fast ; fast < nums.size(); fast++)
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

Array-Easy-搜索插入位置

题面

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 10^4
• -104 <= nums[i] <= 10^4
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 10^4

解答过程

本题要求使用时间复杂度为O(log n)的算法，提示中提到了nums是有序的，结合题意，果断使用二分搜索

代码

int searchInsert(vector<int>& nums, int target) {
        int l = 0 , r = nums.size() - 1 ;
        while (l<=r)
        {
            int mid = (r - l ) / 2 + l ;
            if (target < nums[mid])
            {
                r = mid - 1;
            }
            else if (target > nums[mid])
            {
                l = mid + 1;
            }
            else{
                return mid;
            }
        }
        return l;
    }

Array-Easy-合并两个有序数组

题面

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

解答过程

本题最朴素的思路是合并两个数组后直接进行排序得出结果，但是这样效率太低，我们可以采用双指针的方法，类似归并排序中对子数组的合并，如果从头开始遍历合并，nums1的元素可能在取出前会先被覆盖，所以我们可以从后面开始合并，可以省一部分空间实现原地操作

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0 , p2 = 0;
        int sorted[m + n];
        int cur = 0;
        while (p1 < m || p2 < n)
        {
            if (p1 == m)
            {
                cur = nums2[p2++];
            }
            else if (p2 == n)
            {
                cur = nums1[p1++];
            }
            else if (nums1[p1] < nums2[p2])
            {
                cur = nums1[p1++];
            }
            else{
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (size_t i = 0; i < m + n; i++)
        {
            nums1[i] = sorted[i];
        }
    }