【Day 26 】2022-01-06 - 26.删除排序数组中的重复项

[azl397985856]

26.删除排序数组中的重复项

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

[yetfan]

思路 顺序找过去，有不一样的就 index +1，然后顺手把原位置的数字改了

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        res = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[res] = nums[i]
                res += 1

        return res

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

[yan0327]

思路： 双指针的用法，这道题有道变形题，删除排序数组的重复项II，区别就是与l-k进行判断 思路：顺序遍历，当l<K时，直接左移。当l=k时，开始判断。 如果当前值与nums[l-k]相等，说明数组已经存满当前值，跳过。 否则就赋值加右移

func removeDuplicates(nums []int) int {
    l,k := 0,1
    for r := range nums{
        if l< k||nums[r] != nums[l-k]{
            nums[l] = nums[r]
            l++
        }
    }
    return l
}

时间复杂度O（N） 空间复杂度O（1）

[tian-pengfei]

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

        if(nums.size()<2){
            return nums.size();
        }
        int i=0,j=1;
        for (; j < nums.size();) {
            if(nums[i]==nums[j]){
                nums.erase(nums.begin()+j);
                continue;
            }
            ++i,++j;
        }
        return nums.size();
    }
};

[BpointA]

思路

双指针，类似快慢

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int quick=0;
        int slow=0;
        while(quick<nums.length)
        {
            nums[slow]=nums[quick];
            quick+=1;
            while (quick<nums.length && nums[quick]==nums[quick-1])
            {
                quick+=1;
            }
            slow+=1;
        }
        return slow;

    }
}

[wxj783428795]

思路

1. 双指针，由于是排序数组，所以相同的数字肯定是连续的，所以一次遍历就能解决问题
2. 慢指针先不动，快指针每次前进1
3. 当快慢指针数字相同时，快指针前进1，慢指针不动
4. 当快慢指针数字不同时，把快指针的值赋值给慢指针的下一位，然后快慢指针都前进1
5. 重复3和4直到快指针到数组末尾。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
    let i = 0;
    let j = 1;
    while (j < nums.length) {
        if (nums[i] === nums[j]) {
            j++
        } else {
            nums[i + 1] = nums[j];
            i++;
            j++;
        }
    }
    return i + 1
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[zhy3213]

思路

不要搞骚操作 能删就删 为什么要倒腾

代码

    def removeDuplicates(self, nums: List[int]) -> int:
        fast,slow=1,0
        while fast<len(nums):
            if nums[fast]==nums[slow]:
                while nums[fast]==nums[slow]:
                    fast+=1
                    if fast>len(nums)-1:
                        return slow+1
            nums[slow+1]=nums[fast]
            fast+=1
            slow+=1
        return slow+1

[LannyX]

思路

2 pointers

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int s = 0, f = 0;
        while(f < nums.length){
            if(nums[s] != nums[f]){
                s++;
                nums[s] = nums[f];
            }
            f++;   
        }
        return s + 1;
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[spacker-343]

思路

快慢指针，用 slow 指针保证 [0, slow] 这一段不重复

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[slow] != nums[fast]) {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

复杂度

时间复杂度：O(n) 空间复杂度: O(1)

[nonevsnull]

思路

//s6

• 思路与解法

• 读写 双指针模版题
• 主要是练习写法，简洁清晰；

代码

//s6
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int writer = 0;
        for(int reader = 1;reader < nums.length;reader++){
            if(nums[writer] != nums[reader]){
                writer++;
                nums[writer] = nums[reader];
            }
        }
        return writer+1;
    } 
}

复杂度

//读写双指针 time: O(N) space: O(1)

[CodeWithIris]

Question

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

Note (Fast and slow pointer)

• The fast pointer points to the element that appears for the first time, while the slow pointer points to the element that needs to be modified. Constantly change the values of the fast pointer and the slow pointer until the fast pointer points to the end of the link list.

Solution (C++)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if(n == 0 || n == 1) return n;
        int fast = 1, slow = 1;
        while(fast < n){
            if(nums[fast] != nums[fast - 1]){
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

Complexity

• T: O(n)
• S: O(1)

[zjsuper]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        x = 0
        while x< len(nums)-1:
            if nums[x]<nums[x+1]:
                x +=1
            else:
                nums.pop(x)
        return len(nums)

[feifan-bai]

思路

1. Two points, l, r to traverse the arrays
2. When meet a duplicate element, the l pointer moves forward, the r pointer moves one step and replace the element

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        l, r = 0, 0
        while r < len(nums):
            if nums[l] != nums[r]:
                l += 1
                nums[l] = nums[r]
            r += 1
        return l+1

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[zwmanman]

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <= 1: return 1

    prev = 0
    for i in range(1, len(nums)):
        if nums[prev] != nums[i]:
            prev += 1
            nums[prev] = nums[i]

    return prev + 1

[Bochengwan]

思路

双指针

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        start=0
        length =len(nums)
        for end in range(1,length):
            if nums[start] != nums[end]:
                start+=1
                nums[start] = nums[end]

        return start+1

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[LAGRANGIST]

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

---

题目描述

难度: 简单

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

---

思路（劣）

• 快慢指针：快指针永远在慢指针前一位，如果两个指针所指向数字相同则删除快指针的元素直到结尾

  后文有较好的做法

---

代码（劣）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // trivial cases
        if(nums.size() <= 1) return nums.size();

        int fast = 1,slow = 0;//快慢指针定义

        while(fast < nums.size())
        {   

            while(nums[slow] == nums[fast] && fast < nums.size())
            {
                nums.erase(nums.begin() + fast);
            }
            slow++;
            fast++;
        }
        return nums.size();
    }
};

注意点：

• 快慢指针方法 while 也要加入判断条件防止越界
• erase()中需要传入迭代器，可以通过 nums.begin() + i的方式实现目的

复杂度（劣）

• 未考虑到 vector的 erase函数时间复杂度不是 $O(1)$

---

思路（优）

• 快指针一直走直到遇到不等于慢指针所指数字的元素
• 将慢指针下一位赋值为快指针所在的值
• 慢指针向前走一位

---

代码(优）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //trivial cases 
        if(nums.size() <= 1) return nums.size();
        int l = 0, r = 1;
        while(r<nums.size())
        {
            while(r < nums.size() && nums[r] == nums[l]) r++;
            if(r >= nums.size()) break; 
            else
            {
                nums[l+1] = nums[r];
                l++;
            }
        }
        return l+1;
    }
};

复杂度（优）

• 时间：$O(n)$，$n$ 为 nums.size()
• 空间：$O(1)$

[zwx0641]

class Solution { public int removeDuplicates(int[] nums) { int i = 0, j = 1;

    while (j < nums.length) {
        if (nums[j] != nums[j - 1]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i + 1;
}

}

[laofuWF]

# two pointers
# target_index increment by 1 when nums[target_index] != nums[i]
# updates nums[target_index] = nums[i]

# time: O(N)
# space: O(1)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        target_index = 0

        for i, num in enumerate(nums):
            if num != nums[target_index]:
                target_index += 1
                nums[target_index] = num

        return target_index + 1

[YuyingLiu2021]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:   
        for i in nums[:]:
            if nums.count(i) > 1:
                nums.remove(i)
        return len(nums)

[CoreJa]

思路

• 双指针：一个cnt留在原地，一个快指针依次遍历，cnt仅在发现不同时移动并赋值

代码

class Solution:
    # 双指针：一个cnt留在原地，一个快指针依次遍历，cnt仅在发现不同时移动并赋值
    def removeDuplicates(self, nums: List[int]) -> int:
        cnt = 0
        for num in nums:
            if nums[cnt] != num:
                cnt += 1
                nums[cnt] = num
        return cnt + 1

[ZhangNN2018]

思路

计数

复杂度

• 时间复杂度 O(1)
• 空间复杂度 O(1)

代码

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        k=1
        for i in range(1,len(nums)):
            if nums[i] != nums[i-1]:
                nums[k]=nums[i]
                k=k+1

        return k

[zhangzz2015]

思路

• 使用双指针算法，时间复杂度为O(n)，空间复杂度为O(1)。慢指针指向新的没有重复的vector，快指针指向原始vector。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

        // two pointer. 
        // Space O(n) Space O(1)
        if(nums.size()==0)
            return 0; 
        int count =0; 
        for(int i=1; i< nums.size(); i++)
        {
            if(nums[i]!=nums[count])
            {
                count++;                 
                nums[count] = nums[i]; 
            }
        }
        return count+1; 

    }
};

[LinnSky]

思路

快慢指针

代码

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

复杂度分析

• 时间复杂度O(N)
• 空间复杂度O(1)

[Hacker90]

思路

左右指针

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // if(nums == nullptr)return -1;
        int len = nums.size();
        if(len == 0) return 0;
        int left = 0;
        int right = 0;     
         while(right<len) {
             //最终满足返回要求的数据收集，而非处理重复数据
              if(nums[left]!= nums[right]) {
                  nums[++left]  = nums[right];                 
              }
              right++;
          }

        return left+1;
    }
};

复杂度分析

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

[ZacheryCao]

Idea

Two pointers. Pointer P points to the previous element. Move the other pointer Q forward till it points to the first element not equals to the element P points to. Update P by one, and replace the element it points to to the element pointer Q currently at.

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        ans = 1
        pre = 0
        for i in range(1, len(nums)):
            if nums[i] == nums[pre]:
                continue
            pre += 1
            nums[pre] = nums[i]
            ans += 1
        return ans

Complexity

Time: O(N) Space: O(1)

[tongxw]

思路

读写指针想象成两个独立的数组。写指针指向最后写入的数据。 读指针的值和写指针不相等时，需要写入新数据。

class Solution {
    public int removeDuplicates(int[] nums) {
        int write = 0;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[write]) {
                nums[++write] = nums[read];
            }
        }

        return write + 1;
    }
}

TC: O(N) SC: O(1)

[Alexno1no2]

# 从第一个开始比较，比较其与下一个元素，如果相等，则把这个元素pop出列表
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        Length = len(nums)
        # if Length == 0:
        #     return 0
        i = 0
        for count in range(Length-1):
            if nums[i+1] == nums[i]:
                nums.pop(i)
            else:
                i = i + 1
        return len(nums)

[Husky-Gong]

Solution

• Use 2 pointers
• Left -> unique elements, Right -> current elements

Code

class Solution {
    public int removeDuplicates(int[] nums) {
        int left = 0, right = 0;

        while (right < nums.length) {
            if (left == right) {
                right++;
            } else if (nums[left] == nums[right]) {
                right++;
            } else {
                left++;
                nums[left] = nums[right];
                right++;
            }
        }

        return left + 1;
    }
}

Complexity

Time: O(N) Space: O(1)

[moirobinzhang]

Code:

public class Solution { public int RemoveDuplicates(int[] nums) { if (nums == null || nums.Length == 0) return 0;

    int count = 0;       

    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[count] != nums[i] && count <= i)
        {
            count++;
            nums[count] = nums[i];
        }           
    }

    return count + 1;
}

}

[declan92]

有序、数组、删除重复元素、O(1)额外空间
->双指针读写指针

读写指针

思路
有序数组,重复元素连续分布,删除元素后,相邻元素值不相等;
读写指针;
步骤

1. while循环条件:读指针小于数组长度;
2. 如果读指针的值与写指针的值相等,则读指针++;
3. 不相等写指针++,并将读指针的值赋值给写指针所在位置;
4. 考虑数组为空;
   java

   class Solution {
   public int removeDuplicates(int[] nums) {
       if(nums == null){
           return 0;
       }
       int read = 0,write = 0;
       while(read < nums.length){
           if(!(nums[write] == nums[read])){
               nums[++write] = nums[read];
           }
           read++;
       }
       return write+1;
   }
   }

   时间:O(n)
   空间:O(1)

[Tesla-1i]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        target_index = 0

        for i, num in enumerate(nums):
            if num != nums[target_index]:
                target_index += 1
                nums[target_index] = num

        return target_index + 1

[hdyhdy]

思路： 双指针.

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    slow :=1 
    for fast :=1 ; fast < len(nums) ;fast ++ {
        if nums[fast] != nums[fast - 1]{
            nums[slow] = nums[fast]
            slow ++ 
        }
    }
    return slow 
}

时间复杂度：n 空间复杂度：1

[CodingProgrammer]

思路

快慢指针。slow 指针初始化为0，fast指针初始化为1。fast指针一直往右走，如果 slow 指针指向的值不等于 fast，则将 fast 位置的值赋给 slow + 1 位置。最终返回 slow +1

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        // 思路：快慢指针
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }

        return slow + 1;
    }
}

复杂度

• Time: O(N)
• Space: O(1)

[JudyZhou95]

思路

利用读指针和写指针。读的如果和上一个数字不同就写进写指针的位置，写指针移动一位。读指针每次移动一位，每次操作完之后读记录一下指针位置的数字。

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        read, write = 0, 0
        last_read = None

        while read < len(nums):
            if nums[read] != last_read:
                nums[write] = nums[read]
                write += 1

            last_read = nums[read]  
            read += 1

        return write

复杂度

TC: O(N) SC: O(1)

[xuhzyy]

思路

双指针原地替换数组元素

代码

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0

        left, right = 0, 0
        while right < len(nums) - 1:
            right += 1
            if nums[right] != nums[left]:
                left += 1
                nums[left] = nums[right]
        return left + 1

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[ZJP1483469269]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = r = 1
        n = len(nums)
        while r < n:
            while r < n and nums[r] == nums[r-1]:
                r += 1
            if r < n:
                nums[l] = nums[r]
                l += 1
                r += 1
        return l

[1149004121]

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

思路

使用快慢指针，快指针遍历数组，慢指针指向待修改的位置。

代码

    var removeDuplicates = function(nums) {
        let i = 0;
        let k = 1;
        for(let num of nums){
            if(i < k || nums[i - k] !== num){
                nums[i] = num;
                i++;
            }
        };
        nums.splice(i);
        return i;
    };

复杂度分析

• 时间复杂度：①O(N)，N为数组长度。
• 空间复杂度：①O(1)。

[ivangin]

code:

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] != nums[i]) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }

[linyang4]

思路

1. 维护一个索引index,
2. 遍历数组, 如果数组的第i个元素和第i+1个元素相等, 继续遍历, 如果不相等, 把第i个元素的值维护到第index个元素的位置, 并且index+1

代码

var removeDuplicates = function(nums) {
    let index = 0
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] !== nums[i + 1]) {
            nums[index] = nums[i]
            index++
        }
    }
    return index
};

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[wenlong201807]

代码块

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

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[haixiaolu]

思路

双指针

• 快指针表示遍历数组到达的下标， 慢指针表示下一个不同元素要填入的下标位置
• 两个指针开始的时候都指向下标1， 因为开始的第一位数（下标0）肯定不是重复的，

代码 / Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        fast = slow = 1
        # 将快指针一次遍历从1到n-1的每一个位置
        while fast < n:
            # 如果nums[fast] != nums[fast - 1], 说明nums[fast]和之前的元素都不同
            if nums[fast] != nums[fast - 1]:
                # 将nums[fast]的值复制到nums[slow]中，
                nums[slow] = nums[fast]
                # slow 指向下一个值
                slow += 1
            fast += 1

            # 遍历完， num[0] 到nums[slow - 1]的每个元素都是不相同的
        return slow 

复杂度分析

• 时间复杂度： O(n)
• 空间复杂度： O(1)

[Zhang6260]

JAVA版本

使用双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        //使用双 指针
        int size = nums.length;
        if(size==0)return 0;
        int i=0,j=0;
        for(j=i+1;j<size;j++){
            if(nums[j]!=nums[i]){
                if(j!=i+1){
                    int temp =nums[i+1];
                    nums[i+1]=nums[j];
                    nums[j]=temp;
                }
                i++;
            }
        }
        return i+1;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

[devosend]

思路

双指针

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        index = 0
        for i, num in enumerate(nums):
            if num > nums[index]:
                index += 1
                nums[index] = num

        return index + 1

复杂度分析

• 时间复杂度:O(n)
• 空间复杂度:O(1)

[LuoXingbiao]

思路

快慢指针，遍历一遍数组。

代码

class Solution {
    public int removeDuplicates(int[] nums) {

        int length = nums.length;
        int left = 0;
        int right = 1;

        while(left < length && right < length){
            if(nums[left] != nums[right]){
                nums[left + 1] = nums[right];
                left++;
                right++;
            }
            else{
                right++;
            }
        }

        return left + 1;
    }
}

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

[rootdavid]

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
      int k = 0;

      if (nums.empty()) return 0;

      for (int i = 1; i < nums.size(); i++) {
        if (nums[k] != nums[i]) nums[++k] = nums[i];
      }

      return k + 1;

    }
};

[herbertpan]

思路

1. sorted
2. in-place, no extra space
3. 一个用来填数，一个用来遍历

Code

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }

        int curr = 1;
        int fill = 1;

        while (curr < nums.length) {
            if (nums[curr] != nums[fill - 1]) {
                nums[fill] = nums[curr];
                fill++;
                curr++;
            } else {
                curr++;
            }
        }

        return fill;
    }
}

complexity

time: O(n) space: O(1)

[MonkofEast]

26. Remove Duplicates from Sorted Array

Click Me

Algo

1. DNA

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums: return 0

        slow = quick = 0
        while quick < len(nums):
            if nums[slow] != nums[quick]:
                slow += 1
                nums[slow] = nums[quick]
            quick += 1

        return slow + 1

Comp

T: O(N)

S: O(1)

[charlestang]

思路

使用双指针，slow 指针指向已经整理好的数组的最后一个元素后面。fast 指针用于扫描数组，初始值等于 slow。

用一个变量 pre 记住已经整理好的数组的最后一个值。pre 的初始值是 nums[0]，slow 和 fast 的初始值是 1。

fast 向前遍历，如果发现等于 pre 的值，就跳过，发现不等于 pre 的值，就把它交换到 slow 的位置，更新 pre，然后slow 和 fast 前移。

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

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1
        fast = 1
        n = len(nums)
        if n == 0: return 0
        pre = nums[0]
        while fast < n:
            if nums[fast] != pre:         
                nums[slow] = nums[fast]
                pre = nums[slow]
                slow += 1
            fast += 1
        return slow

[testeducative]

思路

快慢指针

代码

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

[Serena9]

代码

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        r = w = 0
        while r < len(nums):
            if nums[r] != nums[w]:
                w += 1
                nums[w] = nums[r]
            r += 1
        return w+1

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

[biaohuazhou]

思路

采用双指针，因为原数组是有序的 需要一个指针往右边走 找到和前一个不一样的 左指针就把对应的数组位置进行修改

代码

class Solution {
        public int removeDuplicates(int[] nums) {
            if (nums == null) {
                return 0;
            }
            if (nums.length == 1) {
                return 1;
            }
            //第一个数 不用管  所以索引从1开始
            int left = 1, right = 1;
            while (right < nums.length) {
                //如果和前面的不一样
                if (nums[right] != nums[right - 1]) {
                    //就把原数组的对应的位置改变
                    nums[left] = nums[right];
                    left++;
                }
                right++;
            }
            return left;
        }
    }

复杂度分析 时间复杂度： O(n) 空间复杂度：O(1)