[LeetCode]数组相关试题

作者： 华丞臧.
专栏：【LeetCode】
各位读者老爷如果觉得博主写的不错，请诸位多多支持(点赞+收藏+关注)。如果有错误的地方，欢迎在评论区指出。
推荐一款刷题网站 👉 LeetCode刷题网站

---

---

一、移除元素

LeetCode.27 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路：
从示例1可以看出，我们只需要把不等于val的值全部替换到数组的前面，并且返回新的数组的长度也被视为正确答案。
那么给两个标志变量假设为des和src，这两个标志都从数组首元素开始，如果数组src元素的值等于val,则只需要src加一；如果数组src元素的值不等于val的数，把它赋值给数组des处，des和src同时加一；des的值就表示新的数组的长度。

int removeElement(int* nums, int numsSize, int val)
{
    int des = 0;
    int src = 0;
    while(src < numsSize)
    {
        if(*(nums + src) != val)
        {
            *(nums + des) = *(nums + src);
            src++;
            des++;
        }
        else
        {
            src++;
        }
    }
    return des;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

二、删除有序数组中的重复项

LeetCode.26 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:
系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
1
2
3
4
5
6
7
8
9

如果所有断言都通过，那么您的题解将被 通过。

解题思路：
解题思路与27题类似，题目已知给的是一个升序数组，需要 原地 删除重复的元素，并且返回新的数组的长度；那么也给两个标志变量假设为des和src，src用来找不同的值，两个变量均从数组首元素也就0开始；如果des和src位置的元素相等，则只需要把src加一即可；如果src位置的元素与des处的元素不相等，则先给des加一再把src的值放入数组des处，src加一；这里需要注意程序结束des表示的是数组元素的下标，所以数组元素个数等于 des+1。

int removeDuplicates(int* nums, int numsSize)
{
    int des = 0;
    int src = 0;
    while(src < numsSize)
    {
        if(*(nums + des) < *(nums + src))
        {
            des++;
            *(nums + des) = *(nums + src);
            src++;
        }
        else
        {
            src++;
        }
    }
    return des+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、合并两个有序数组

LeetCode.88 合并两个有序数组

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

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

解题思路：
合并数组nums1和nums2,并且将合并后的数组存放在nums1中，数组是 非递减顺序 也就是说后面的元素大于前面的元素；既然合并后的数据是存放在nums1数组当中的，那么我们不妨从后往前比较两个数组的元素取其中的较大值依次放入nums1的数组尾部(合并后的数组尾部)，当两个数组都遍历完就可以的到合并后的nums1。
注意：需要分两种情况，nums1先走完和nums2先走完。

• 情况一：nums2先走完

nums2先走完，则不需要额外的操作，因为nums1本就是 非递增顺序且保存在nums1数组中。

• 情况二：nums1先走完

nums1先走完，则会跳出循环，这时nums2还有元素没有放入到nums1数组当中，所以需要继续把nums2的剩余数据放入nums1中。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int end1 = m -1;
    int end2 = n -1;
    int end = m + n - 1;
    while(end1 >=0 && end2 >= 0)
    {
        if(nums1[end1] < nums2[end2])
        {
            nums1[end] = nums2[end2];
            end2--;
            end--;
        }
        else
        {
            nums1[end] = nums1[end1];
            end1--;
            end--;
        }
    }
    while(end2 >= 0)
    {
        nums1[end] = nums2[end2];
        end--;
        end2--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27