LeetCode 26 Remove Duplicates from Sorted Array

Tag: 数组类题目 LeetCode Posted on 2022-02-13 19:26:01 Edited on 2022-02-13 20:07:26 Views: 150

概述

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

题目要求 in place 操作,O(1) 空间复杂度。

暴力法

O(n^2) 的时间复杂度,每次遇到重复值都把后面的整体向前移动一位。

实现的时候注意移动后要手动 l --,因为 nums[l] 的值已经改变,需要重新经过循环体判断。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l, r;
        for (l = 1, r = nums.size(); l < r; l ++) {
            if (nums[l] == nums[l - 1]) {
                for (int i = l; i + 1 < r; i ++) {
                    nums[i] = nums[i + 1];
                }
                r --;
                l --;
            }
        }
        return r;
    }
};

TLE 了。

快慢指针法

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int s, f;
        for (s = 1, f = 1; f < nums.size(); f ++) {
            if (nums[f] != nums[f-1]) {
                nums[s++] = nums[f];
            }
        }
        return s;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/