数据结构顺序表力扣例题AC——代码以及思路记录

顺序表力扣例题

27.移除元素

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

AC：

int removeElement(int* nums, int numsSize, int val) {
    int src = 0;
    int dst = 0;
    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst;
}

代码思想：
双指针，都指向起始位置，src负责检索数组中的元素并比较与val的关系，dst负责记录符合条件的个数（并保存符合条件的元素，小于当前位置的都符合）。当src指向的元素与val相同的时候src就跳过（不符合就不用管，且可以被覆盖），不相同则用src位置元素将dst所指位置的元素覆盖，两个指针都继续向前走一位，直到检索完整个数组。dst仅会保存符合要求的元素，此时所指位置就是符合要求的个数，返回dst就可以。

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

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

int removeDuplicates(int* nums, int numsSize) {
    int src = 0;
    int dst = 0;
    while(src < numsSize)
    {
        if(nums[src] != nums[dst])
        {
            nums[++dst] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst+1;
}

代码思想：
双指针，都指向起始位置，src负责检索数组中的元素并比较与dst所指位置元素的关系，dst负责记录符合条件的个数（并保存符合条件的元素，小于当前位置的都符合）。当src指向的元素与dst相同的时候src就跳过（不符合就不用管，且可以被覆盖，因为dst一定小于等于src），不相同则先将dst++（画图便可以看出此时dst所指的数字是符合的，因为第一个数肯定不需要被覆盖，且此时dst并没有移动，所以后边需要跳过此数再进行覆盖，所以需要先++，代码中写为++dst），再用src位置元素将dst所指位置的元素覆盖，src继续向前走一位，直到检索完整个数组。dst仅会保存符合要求的元素，此时所指位置就是符合要求的最后一位元素，由于下标是0开始，最后需要返回dst+1（在这里最后返回不可以用dst++，但可以用++dst，因为前者先return再++，但是return后程序就直接结束了，但是++dst会先执行++，所以也是可以的）。

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i1 = m-1;
    int i2 = n-1;
    int j = m+n-1;

    while(i1 >= 0 && i2 >= 0)
    {
        if(nums1[i1] > nums2[i2])
        {
            nums1[j--] = nums1[i1--];
        }
        else
        {
            nums1[j--] = nums2[i2--];
        }
    }
    //考虑当nums1都结束但是nums2仍有未比较完的的情况
    while(i2 >= 0)
        {
            nums1[j--] = nums2[i2--];
        }
}

代码思路：
有几种思路可以写，①新建一个数组，依次遍历nums1和nums2，并进行比较，加入到新数组中；②将nums2直接合并到nums1中然后进行排序；第一种方法时间复杂度O(n)，第二种O(n^2)，所以优先考虑①，但是题目中要求最后提交的是nums1数组，所以不能新建数组，观察nums1，他的m个元素以后就都是0，则可以把m个元素以后的由0组成的那部分视为新数组，然后倒着进行比较，也就是先比较大的，然后哪个大哪个覆盖末尾的0，指针前移，因此需要三个指针，分别是i1，i2，进行比较，j用来记录当前nums1添加进去的元素个数和位置。此外还需要考虑在哪里程序终止，①当i2遍历完以后，i1剩余的本身就是非递减顺序，所以可以直接停止；②当i1遍历完但是i2还有未比较的数字时，仍然需要添加到nums1中，因为最终要的是nums1，所以还需要单独考虑一次这种情况（代码中有注释提示）；函数返回类型是void，因此不需要return。