顺序表(二)(数据结构)

一. 顺序表算法题

1.1 移除元素

题目：https://leetcode.cn/problems/remove-element/description/

给你一个数组

nums

• *和一个值

  val
  

  ，你需要原地移除所有数值等于

  val
  

• *的元素。元素的顺序可能发生改变。然后返回

  nums
  

  中与

  val
  

  不同的元素的数量。假设

  nums
  

  中不等于

  val
  

  的元素数量为

  k
  

  ，要通过此题，您需要执行以下操作：更改

  nums
  

  数组，使

  nums
  

  的前

  k
  

  个元素包含不等于

  val
  

  的元素。

  nums
  

  的其余元素和

  nums
  

  的大小不重要。返回

  k
  

  。当我们看到这个题目的时候，脑子里首先想到的可能是我们可能会创建一个新的数组，然后将不是val的值放在这个新的数组中，最后在返回k，这个方法是可行的，但其实就是空间换时间的做法，这里有一个更好的方法，使用两个指针的方法去遍历数组。

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

我们在写算法的时候最重要的是我们的思路，我们该怎么去想，不是为了去解出这个题，而是我们的思路，要扩大我们的思路，多思考，再借鉴别人代码的时候，注意关注的是别人的思路，多多积累一些算法的思路。

1.2 删除有序数组中的重复项

题目：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

给你一个 非严格递增排列 的数组

nums

，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回

nums

中唯一元素的个数。考虑

nums

的唯一元素的数量为

k

，你需要做以下事情确保你的题解可以被通过：更改数组

nums

，使

nums

的前

k

个元素包含唯一元素，并按照它们最初在

nums

中出现的顺序排列。

nums

的其余元素与

nums

的大小不重要。返回

k

。

我们看上面的图片，假如现在数组中是1 1 2，现在我们要删除重复项的元素，那么结果应该是1 2，我们可以先使用两个指针，str指向数组的第一个元素，dst指向数组的第二个元素，第一步先将它们两者比较，如果是相等的，仅仅让dst这个指针向后移动一位，再次进行比较，如果此时不相等的话， 就如上图，dst向后移动了一位指向了元素2，它与原本的str指针不相等了，此时就让str指针也向后移动一位，再将dst的值赋给str，最后再让dst++，跳出循环，但是最终我们要返回的是与元素的个数，所以return str+1。

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

1.3 合并两个有序数组

题目：https://leetcode.cn/problems/merge-sorted-array/description/

给你两个按 非递减顺序 排列的整数数组

nums1

• *和

  nums2
  

  ，另有两个整数

  m
  

  和

  n
  

  ，分别表示

  nums1
  

  和

  nums2
  

  中的元素数目.请你 合并

  nums2
  

• *到

  nums1
  

  中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组

  nums1
  

  中。为了应对这种情况，

  nums1
  

  的初始长度为

  m + n
  

  ，其中前

  m
  

  个元素表示应合并的元素，后

  n
  

  个元素为

  0
  

  ，应忽略。

  nums2
  

  的长度为

  n
  

  。

在这个题目中，我们首先要注意的是题目中已经给出两个数组是有序的数组，所以我们脑海中应该出现的第一种思路是，我们先比较谁大是不是更方便一点，所以我们创建三个指针，分别指向m和n的位置以及较长数组的最后一位，如下图：

我们先比较来l2和l1的大小，两者谁大，便将其赋值给l3的位置，随后l3--，l2和l1谁大谁--，这样依次比较下去，但是我们的循环总是要有一个条件，所以刚开始进入循环的条件应该是l1>=0&&l2>=0，但是当我们第一个循环结束之后，我们的目标却不一定完成，因为我们的目的是将所有数据有序的存放在num1中，假如当先小于0，那么就是说num2中的数据已经全部放在了num1中，就不需要处理了，但是当l1先小于0，那么我们还需要将num2中的数据依次再放入num1中，才算最终完成任务。

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(nums1[l1]>nums2[l2])
        {
            nums1[l3--]=nums1[l1--];
            //dst--;
            //str2--;
        }
        else
        {
            nums1[l3--]=nums2[l2--];
            //str2--;
            //str1--;
        }
    }
    while(l2>=0)  
    {
        nums1[l3--]=nums2[l2--];
        //str2--;
        //dst--;
    }  

二. 顺序表问题与思考

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

上面的这些问题是我们在顺序表中能清晰感受到的问题，如何解决这些问题呢?我们接下来学习的链表会解决这些问题。