leetcode with python:26. Remove Duplicates from Sorted Array

题目:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory

说真的一开始看到这题我完全看不懂它想表达什么,后来才了解是要return这个阵列有几个不同的数(k),同时把这些数按序移到阵列最前面
题目最后一行有说不能再开其他阵列,意即我们仅能在这个阵列上进行操作
ex:[0,0,1,1,1,2,2,3,3,4]==>return k=5 ,而此时的阵列为[0,1,2,3,4,,x,x,x,x] (x为任意值)

不过多亏input是sorted的阵列,让整题容易许多

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

由于我们只要将阵列中的值各选一个做代表,移到前面k项,后面的值便可以随意
因此当我们一侦测到前后值不一时,便表示出现了新的值(因为input是sorted list)
将遇到的新值往前面放,k代表了下次遇到新值要放的index,同时也能作为最后的回传值(共有几个相异值)
最后执行时间为93ms(faster than 88.54%)

那我们下题见