LeetCode刷题之旅（简单-8）：删除排序数组中的重复项

LeetCode刷题之旅（简单-8）：删除排序数组中的重复项

2019年5月15日

目录

​​题目：删除排序数组中的重复项​​

​​解决方法一：双指针，快指针遍历，慢指针赋值项​​

​​性能结果：​​

​​小结：​​

​​解决方法二：思路差不多的方法，但是代码写的好简洁​​

​​思路：​​

​​分析：​​

​​解决方法三：稍微耗时耗内存，但也是最容易想到的方法​​

​​总结：​​

题目：删除排序数组中的重复项

解决方法一：双指针，快指针遍历，慢指针赋值项

package leetCode;/** * Date: 2019/5/14 14 :32 * * @author */public class DeleteDuplicatesInSortedArrays { public static void main(String[] args){ // 1 2 2 3 3 4 int[] array = {1,2,2,2,3,3,4};// int[] array = {1,1,2}; int i = removeDuplicates(array); System.out.println("i="+i); for (int j=0;j

性能结果：

小结：

开拓了思路：使用指针的方法，达到明确对比的方式；时间复杂度为O（n），只用循环一次；空间复杂度也是O（n）；算法无敌！

解决方法二：思路差不多的方法，但是代码写的好简洁

public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1;}

思路：

算法数组完成排序后，我们可以放置两个指针 ii 和 jj，其中 ii 是慢指针，而 jj 是快指针。只要 nums[i] = nums[j]nums[i]=nums[j]，我们就增加 jj 以跳过重复项。当我们遇到 nums[j] \neq nums[i]nums[j]=nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]nums[j]）的值复制到 nums[i + 1]nums[i+1]。然后递增 ii，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。

分析：

时间复杂度：O(n)O(n)，假设数组的长度是 nn，那么 ii 和 jj 分别最多遍历 nn 步。空间复杂度：O(1)O(1)。

解决方法三：稍微耗时耗内存，但也是最容易想到的方法

class Solution { public int removeDuplicates(int[] nums) { int count = nums.length; if(count <= 0) return 0; int key; for(int i = 0; i < count; i++){ key = nums[i]; for(int j = i+1; j < count; j++){ if(key == nums[j]){ //发现相同元素，所有后面的元素前移一位 for(int p = j; p < count-1; p++){ nums[p] = nums[p+1]; } count--; j--; //由于后面元素前移了，还需要检验这个移过来的元素是否重复 } } } return count; }}

这个方法也是很巧妙的，跟我一开始的想法差不多。由左边开始，设置第一个是标记值，然后遍历寻找后面和标记值相同的值，如果找到，相同值的后面值依次前移一位，对比数组 长度减一。这样个方式想法简单，时间复杂度O(n^2)，但是最容易想出来

总结：

数组，不变的核心啊！结合循环，判断，然后组成了各种各样的数据结构，服！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。