【数据结构之顺序表系列】顺序表常见面试题汇总_顺序表面试题

前言

本文主要总结博主平时做过的顺序表的OJ题，持续更新~

一、移除元素

题目：

提交代码：

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

提交结果：

思路分析：
本题主要采用双指针来解决问题，同时，我们需要将一个数组想象成两个数组。原来的题目只给了一个数组，但是这里，我们需要将这个数组想象成两个数组，一个充当存放原来数据的数组，另一个充当存放最终数据的目标数组。此时，我们需要两个指针：src和dst，src指针遍历原来的数组，dst指向目标数组，遍历过程，src依次遍历原来的数组，当指向的值与题目给定的值相等时，则继续指向下一个位置，当指向的值和题目给定的值不相等时，则将该值放入目标数组中dst指向的位置，再让src和dst分别指向空间的下一个位置，直到src将原来数组遍历完成之后就结束。

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

题目：

提交代码：

int removeDuplicates(int* nums, int numsSize){
   // 双指针法
   int src = 1,dst = 0;
   while(src<numsSize)
   {
       if(nums[src] == nums[src-1])
       {
           // 相邻的元素是相等的，也就是这个元素是重复出现的元素
           src++;
       }
       else
       {
           // 相邻的元素不相等了，src-1位置的值就是上一轮元素最后出现的位置
           nums[dst] = nums[src-1];
           dst++;
           src++;
       }
   }
   // 一定要将最后一个元素处理过去
   nums[dst] = nums[src-1];
   dst++;
   return dst;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

提交结果：

思路分析：
本题同样采用的是双指针的方法来解决问题，但是相比于上题有所变化。同样需要将题目给定的数组看成两个数组，一个是存放原来数据的数组，另一个是存放最终数据的数组。此时需要两个指针:src和dst，与上题不同的是，这个题目中我们让src从1开始，也就是从原来数组中的第二个位置开始，dst仍然从第一个位置开始，遍历过程：不断让src位置的值和前一个位置的值进行相比，如果src位置的值和上一个位置的值相等，说明该值为重复元素，src指向下一个位置，当src位置的值和前一个位置的值不相等时，说明重复出现的元素区间已经遍历完，此时src位置的前一个位置的值就是已经刚遍历完的重复出现的元素最后一次出现的位置，此时，需要将该位置的值赋给dst指向的位置，并让src和dst分别指向下一个位置，直到src遍历到最后一个数据的下一个位置时循环结束。当循环结束时，我们需要知道，使用上面这种方法，最后一个位置的元素无论重复与否，都没有被放入目标数组中，所以，当循环结束时，我们需要强制性让原来数组最后一个位置的元素放入目标数组，根据dst和数组元素个数的关系，我们知道最终返回dst即可。

三、合并两个有序数组

题目：

提交代码：
提交结果：
思路分析：