[leetcode]27. 移除元素（Java实现）

题目

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

解法1：

这个题好像简单一些，很快就能想出来。

我的逻辑是，双指针找到val和数组末尾不是val的数字对换，这样所有的val最后都会留在数组末端。指针i从前往后遍历，指针j从后往前，j以后的数字保证全是val，所以循环内条件写i<j就好啦。

时间复杂度O(n)，空间复杂度O(1)。

解法2：

这个是看题解看到的，我觉得他的思路挺简单的，找到不是val的数字就拷贝到数组前面去，因为题目中有说无所谓数组后面是什么。

不过不知道为什么，他这种方式消耗的内存反而比我的稍微大一些，是反复拷贝的原因吗？我有点不明白。

总结

我今天到这儿才做完小红书学长规定的第一天刷题内容。。拖拉死了。做数组题就是要想着：绝对不要用双层循环啊啊啊。而且有时候感觉自己会想的比较复杂，看题解的一些简单清奇思路会豁然开朗。