521. Remove Duplicate Numbers in Array
中文EnglishGiven an array of integers, remove the duplicate numbers in it.
You should:
Do it in place in the array.
Move the unique numbers to the front of the array.
Return the total number of the unique numbers.
样例Example 1:
Input:
nums = [1,3,1,4,4,2]
Output:
[1,3,4,2,?,?]
4
Explanation:
Move duplicate integers to the tail of nums => nums = [1,3,4,2,?,?].
Return the number of unique integers in nums => 4.
Actually we don’t care about what you place in ?, we only care about the part which has no duplicate integers.
Example 2:
Input:
nums = [1,2,3]
Output:
[1,2,3]
3
挑战
Do it in O(n) time complexity.
Do it in O(nlogn) time without extra space.
注意事项You don’t need to keep the original order of the integers.
O(n)算法
思想：定义一个set保存查看过的元素集合，两个异向指针，end标记查看过的元素
class Solution:"""@param nums: an array of integers@return: the number of unique integers"""def deduplication(self, nums):# write your code herenums_one = set()start = 0end = len(nums)-1while (start<=end):# TODO: write code...:if nums[start] in nums_one:nums[start], nums[end] = nums[end], nums[start]end -= 1else:nums_one.add(nums[start])start += 1return start
O(nlogn)算法：
思想：先排序，然后定义两个同向指针，快指针找不同的元素，慢指针指向重复元素的第一个的后面一个，然后进行替换
class Solution:"""@param nums: an array of integers@return: the number of unique integers"""def deduplication(self, nums):# write your code herenums = sorted(nums)slow = 0fast = 0n = len(nums)while (fast < n):if nums[slow] == nums[fast]:fast += 1 else:slow += 1 nums[slow] = nums[fast]fast += 1return slow+1
运行结果明明是对的，但是给报错了，可能是lintcode的bug