数组-重复的元素

有多个重复元素

1
2
3
4

dups([1, 2, 3])    = []
dups([1, 2, 2])    = [2]
dups([3, 3, 3])    = [3]
dups([2, 1, 2, 1]) = [1, 2]

注意的问题：

1. 结果是否要求有序?
2. 结果本身是否可以包含重复元素?

思路：

1. 蛮力
2. set - O(N) - time O(N) - space
3. Sort - O(NlogN)

未挖掘信息: 1 <= x <= len(array)

0 <= x-1 <= len(array)-1 可作为下标

Encoding

检查是否有重复元素

217. Contains Duplicate

nums[i] = nums[j] ?

用正负

219. Contains Duplicate II

nums[i] = nums[j] && abs(i-j) <= k

下标之间满足某种性质时,可考虑用滑动窗口

220. Contains Duplicate III

abs(nums[i] - nums[j]) <= t && abs(i-j) <= k

要比较离nums[i]最近的数nums[j]的差值最多为t，可能大于nums[i],也可能小于nums[i],就需要用到BST。

但是有abs(i-j) <= k，所以BST的容量最多为k。

删除重复元素

27. Remove Element

删除所有目标元素val

方法1：

通过双指针来改变数组中的值。slow表示当前应该保存的长度，fast用来向前遍历，如果遇到和val相同的元素就跳过，不同的就把nums[slow]的值用nums[fast]的值覆盖掉。

方法2：

当要删除的元素比较少时，方法1会做了很多不必要的拷贝操作。比如: nums=[1,2,3,5,4] val=4。

同样使用双指针，只不过这次时一前(i)一后(j)，当遍历数组时，遇到和val相同的元素时，可以把这个元素和数组最后的元素nums[j]交换，并把后指针向前移动一个位置。

但是如果如果交换过来的元素仍然是你想删除的元素，那么在交换完后不要移动前指针i，这样一次循环后可以保证的是后指针j的元素可以移动到改到的位置，前指针i不一定。

26. Remove Duplicates from Sorted Array

重复的元素只允许出现1次

1
2
3
4
5
6
7
8
9
10
11

while(fast < N)
{
    if( nums[fast] != nums[slow]) // the duplicate run has ended 
    {
        slow++; // keep only one of duplicate, nums[slow] is the only one 
        nums[slow] = nums[fast]; // copy its value to nums[slow+1]
    }
    fast++;
}
return slow+1;

80. Remove Duplicates from Sorted Array II

重复的元素至多出现2次

如何保证至多？

i和n两个指针，一开始齐头并进，同时指向一个位置，当当前的数值不必他前前一个数值大的时候，意味着出现了3个或3个以上的相同值，此时不满足if条件，i停留在不满足的位置，等待下一个更大的数来替换，当出现下一个更大的数字时再次满足if条件，将i所指向的位置替换为该数字，i指向下一个等待替换，此时if条件再次用以检测用来替换的数字，以保证不出现两次以上的重复。

1
2
3
4
5
6
7
8
9
10

int i = 0; 
for(int e: nums)
{
    if( i < 2 || e > nums[i-2] )
    {
        nums[i] = e;
        i++;
    }
}
return i;

寻找重复元素

287. Find the Duplicate Number (重复1个元素)

442. Find All Duplicates in an Array

some elements appear twice and others appear once. Find all the elements that appear twice in this array.

使用负负得正的标记法，注意与448. Find All Numbers Disappeared in an Array的区别。

Comments: