-
Notifications
You must be signed in to change notification settings - Fork 0
/
026 Remove Duplicates from Sorted Array.py
executable file
·69 lines (55 loc) · 1.88 KB
/
026 Remove Duplicates from Sorted Array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
"""
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
"""
__author__ = 'Danyang'
class Solution:
def removeDuplicates(self, A):
"""
Algorithms: Two Pointers, open & closed
Data structure: array
Shifting the array
del, pop(), or remove() are not allowed.
return the length of "shrunk" array
The array remains the same length
:param A: list
:return: "shrunk" list
"""
length = len(A)
# trivial
if length==0 or length==1:
return length
# closed pointer, open pointer
closed_ptr = 0
open_ptr = 1
while open_ptr<length:
# find the next non-duplicate:
if A[closed_ptr]==A[open_ptr]:
open_ptr += 1
continue # go to the next iteration
non_duplicate = A[open_ptr]
A[closed_ptr+1] = non_duplicate
closed_ptr += 1
return closed_ptr+1 # length is index+1
def removeDuplicates_another_loop_style(self, A):
"""
Yet another looping style - double while loops
:param A: list
:return: "shrunk" list
"""
length = len(A)
if length==0 or length==1:
return length
closed_ptr = 0
open_ptr = 1
while open_ptr<length:
while open_ptr<length and A[closed_ptr]==A[open_ptr]:
open_ptr += 1
if open_ptr<length:
non_duplicate = A[open_ptr]
A[closed_ptr+1] = non_duplicate
closed_ptr += 1
return closed_ptr+1 # length is index+1