Java教程

2_26.删除有序数组中的重复项

本文主要是介绍2_26.删除有序数组中的重复项，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述：
image
解题思路

  • 第一思路：
    第一反应就是双指针法，但是在写代码的时候，细节没能处理好，导致修改了很多次，才提交成功。自己的双指针法，是个假的双指针，甚至需要三个变量去描述这个双指针，有点拉胯，还是没能深刻理解双指针fast和slow的内涵。
  • 题解双指针法：
    由于有序数组，那么对于任意的i < j,如果nums[i] = nums[j],对于任意的i <= k <= j,都必有num[i] = nums[k] = nums[j],因此定义两个指针fast和slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标1。
    假设数组nums的长度为n。将快指针fast依次遍历从1到n-1的每个位置，对于每个位置，如果nums[fast] != nums[fast - 1],说明nums[fast]和之前的元素都不同，因此将nums[fast]赋值到nums[slow]，然后将slow的值加1，也即指向下一个位置。
    遍历结束后，返回slow即可。

代码：

自己写的烂代码 
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int pos = 0;//用于记录当前遍历的位置
        int i = 0;
        for (i = 0; i < len - 1; i++){
            int j = pos + 1;
            while (j < len && nums[j] == nums[i]){//需要判断是否越界
                j = j + 1;
            }
            if (j >= len){//如果是j >= len这种跳出循环的情况，说明要越界了
                return i + 1;
            }
            nums[i + 1] = nums[j]; //没越界，赋值给下一个元素
            pos = j;
            if (j == len - 1){ // 如果此时j是最后一个元素，并且nums[i] != nums[j],则最后一个元素也是不同的元素
                return i + 2;
            }
        }
        return i + 1;
    }
}
双指针法 
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}
这篇关于2_26.删除有序数组中的重复项的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航