【数据结构】_顺序表经典算法OJ（力扣版）

目录

1. 移除元素

1.1 题目描述及链接

1.2 解题思路

1.3 程序

2. 合并两个有序数组

1.1 原题链接及题目描述

1.2 解题思路

1.3 程序

1. 移除元素

1.1 题目描述及链接

原题链接：27. 移除元素 - 力扣（LeetCode）

题目描述：        

        给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
        假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
        更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
        返回 k。

1.2 解题思路

思路1：

创建新数组，遍历源数组，将不为val的值依次放到新数组中（不满足空间复杂度要求）；

思路2：（双指针法）

创建两个变量src与dst作为下标用于遍历数组，若src指向的值为val，则src++；若src指向的值不为val，则令nums[dst]=nums[src]，并令src++，dst++；直到src超过数组元素个数时，dst即nums数组的不等于val的个数；

1.3 程序

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

2. 合并两个有序数组

1.1 原题链接及题目描述

原题链接：88. 合并两个有序数组 - 力扣（LeetCode）

题目描述：

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

1.2 解题思路

思路1：

先将num2中的数据依次放入到num1数组有效数据的后面，再用排序算法对num1数组进行排序；

（依赖于排序算法的复杂度）

思路2：（从后往前比大）

创建两个变量l1和l2分别用于从后往前依次遍历数组num1和num2，初始时l1和l2分别指向数组num1和num2最后一个有效元素。再创建变量l3,指向数组num1最后一个元素；

比较num[l1]与num[l2]，将较大的赋值给num1[l3]，并令其指向的位置前移，直至l2指向位置越出num2界限；

注：对于循环终止条件，若l2先于l1指向数组前而越界，说明num2中元素已全部放置于num1数组中，无需再额外操作；若l1先于l2指向数组前而越界，则说明num2中元素尚未全部放置于num1数组中，仍需进行后续的放置操作；

1.3 程序

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1=m-1;
    int l2=n-1;
    int l3=m+n-1;
    while(l1>=0 && l2>=0){
        if(nums2[l2]>nums1[l1]){
            nums1[l3]=nums2[l2];
            l3--;
            l2--;
        }else{
            nums1[l3]=nums1[l1];
            l3--;
            l1--;
        }
    }
    // l1<0 or l2<0
    while(l2>=0){
         nums1[l3]=nums2[l2];
            l3--;
            l2--;
    }
}