0


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

一. 顺序表算法题

1.1 移除元素

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

给你一个数组

  1. nums
  • *和一个值
    1. val
    ,你需要原地移除所有数值等于
    1. val
  • *的元素。元素的顺序可能发生改变。然后返回
    1. nums
    中与
    1. val
    不同的元素的数量。假设
    1. nums
    中不等于
    1. val
    的元素数量为
    1. k
    ,要通过此题,您需要执行以下操作:更改
    1. nums
    数组,使
    1. nums
    的前
    1. k
    个元素包含不等于
    1. val
    的元素。
    1. nums
    的其余元素和
    1. nums
    的大小不重要。返回
    1. k
    。当我们看到这个题目的时候,脑子里首先想到的可能是我们可能会创建一个新的数组,然后将不是val的值放在这个新的数组中,最后在返回k,这个方法是可行的,但其实就是空间换时间的做法,这里有一个更好的方法,使用两个指针的方法去遍历数组。

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

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

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

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

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

  1. nums

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

  1. nums

中唯一元素的个数。考虑

  1. nums

的唯一元素的数量为

  1. k

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

  1. nums

,使

  1. nums

的前

  1. k

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

  1. nums

中出现的顺序排列。

  1. nums

的其余元素与

  1. nums

的大小不重要。返回

  1. k

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

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

1.3 合并两个有序数组

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

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

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

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

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

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

二. 顺序表问题与思考

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

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

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

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


本文转载自: https://blog.csdn.net/OKkankan/article/details/143218694
版权归原作者 OKkankan 所有, 如有侵权,请联系我们删除。

“顺序表(二)(数据结构)”的评论:

还没有评论