Java教程

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

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

题目描述:
image
解题思路

  • 第一思路:
    第一反应就是双指针法,但是在写代码的时候,细节没能处理好,导致修改了很多次,才提交成功。自己的双指针法,是个假的双指针,甚至需要三个变量去描述这个双指针,有点拉胯,还是没能深刻理解双指针fastslow的内涵。
  • 题解双指针法:
    由于有序数组,那么对于任意的i < j,如果nums[i] = nums[j],对于任意的i <= k <= j,都必有num[i] = nums[k] = nums[j],因此定义两个指针fastslow 分别为快指针和慢指针,快指针表示遍历数组到达的下标位置,慢指针表示下一个不同元素要填入的下标位置,初始时两个指针都指向下标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.删除有序数组中的重复项的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!