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

一. 顺序表算法题

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--;}