Skip to content

Commit 0fdb464

Browse files
Meto TrajkovskiMeto Trajkovski
Meto Trajkovski
authored and
Meto Trajkovski
committed
Added and updated pivoting solutions
1 parent 0237794 commit 0fdb464

4 files changed

Lines changed: 296 additions & 104 deletions

File tree

‎Lists/k_closest_points.py‎

Lines changed: 45 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -9,34 +9,37 @@
99
=========================================
1010
Same solution as the nth_smallest.py, in this case we're looking for the K smallest DISTANCES.
1111
Based on the quick sort algorithm (pivoting, divide and conquer).
12-
More precisly in-place quick sort (without using additional space).
12+
More precisly in-place quick sort. Recursive solution.
1313
Time Complexity: O(N) , O(N + N/2 + N/4 + N/8 + ... + 1 = 2*N = N)
1414
Space Complexity: O(K) , length of the output array
15+
Completely the same algorithm as the previous one, but without recursion. This solution is cleaner.
16+
Time Complexity: O(N)
17+
Space Complexity: O(K)
1518
'''
1619

1720

18-
############
19-
# Solution #
20-
############
21+
##############
22+
# Solution 1 #
23+
##############
2124

22-
def find_k_closes(arr, pt, k):
25+
def find_k_closes_recursive(arr, pt, k):
2326
n = len(arr)
2427
if k > n:
25-
return None
28+
return arr
2629
if k < 1:
27-
return None
30+
return []
2831

2932
kth_closest(arr, k - 1, 0, n - 1, pt)
3033

3134
return arr[:k]
3235

33-
def kth_closest(arr, n, left, right, pt):
36+
def kth_closest(arr, k, left, right, pt):
3437
pivot = pivoting(arr, left, right, pt)
3538

36-
if pivot > n:
37-
kth_closest(arr, n, left, pivot - 1, pt)
38-
elif pivot < n:
39-
kth_closest(arr, n, pivot + 1, right, pt)
39+
if pivot > k:
40+
kth_closest(arr, k, left, pivot - 1, pt)
41+
elif pivot < k:
42+
kth_closest(arr, k, pivot + 1, right, pt)
4043

4144
def pivoting(arr, left, right, pt):
4245
# O(N) pivoting
@@ -69,15 +72,45 @@ def sqr_dist(a, b):
6972
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
7073

7174

75+
##############
76+
# Solution 2 #
77+
##############
78+
79+
def find_k_closes(arr, pt, k):
80+
n = len(arr)
81+
if k > n:
82+
return arr
83+
if k < 1:
84+
return []
85+
86+
k -= 1
87+
left = 0
88+
right = n - 1
89+
90+
while True:
91+
pivot = pivoting(arr, left, right, pt) # the same method from the previous solution
92+
93+
if pivot > k:
94+
right = pivot - 1
95+
elif pivot < k:
96+
left = pivot + 1
97+
else:
98+
return arr[:k + 1]
99+
100+
# not possible
101+
return None
102+
72103

73104
###########
74105
# Testing #
75106
###########
76107

77108
# Test 1
78109
# Correct result => [(2, 2), (2, 1.5), (2, 1)]
110+
print(find_k_closes_recursive([(0, 1), (3, 3), (1, 2), (2, 1.5), (3, -1), (2, 1), (4, 3), (5, 1), (-1, 2), (2, 2)], (2, 2), 3))
79111
print(find_k_closes([(0, 1), (3, 3), (1, 2), (2, 1.5), (3, -1), (2, 1), (4, 3), (5, 1), (-1, 2), (2, 2)], (2, 2), 3))
80112

81113
# Test 2
82114
# Correct result => [(1, 2), (2, 1)]
115+
print(find_k_closes_recursive([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))
83116
print(find_k_closes([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))

‎Lists/kth_smallest.py‎

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
'''
2+
K-th Smallest Number
3+
4+
Find the K-th smallest number in an unordered list.
5+
6+
Input: [6, 2, 4, 8, 10, 1, 11], 1
7+
Output: 0
8+
9+
Input: [6, 2, 4, 8, 10, 0, 11], 2
10+
Output: 2
11+
12+
Input: [6, 2, 4, 8, 10, 0, 11], 4
13+
Output: 6
14+
15+
=========================================
16+
This solution is based on the quick sort algorithm (pivoting, divide and conquer).
17+
More precisly in-place quick sort. Recursive solution.
18+
Time Complexity: O(N) , O(N + N/2 + N/4 + N/8 + ... + 1 = 2*N = N)
19+
Space Complexity: O(LogN) , because of the recursion stack (if this doesn't count, then O(1))
20+
Completely the same algorithm as the previous one, but without recursion. This solution is cleaner.
21+
Time Complexity: O(N)
22+
Space Complexity: O(1)
23+
'''
24+
25+
26+
##############
27+
# Solution 1 #
28+
##############
29+
30+
def find_kth_smallest_recursive(arr, k):
31+
n = len(arr)
32+
if k > n:
33+
return None
34+
if k < 1:
35+
return None
36+
return kth_smallest(arr, k - 1, 0, n - 1)
37+
38+
def kth_smallest(arr, k, left, right):
39+
pivot = pivoting(arr, left, right)
40+
41+
if pivot > k:
42+
return kth_smallest(arr, k, left, pivot - 1)
43+
if pivot < k:
44+
return kth_smallest(arr, k, pivot + 1, right)
45+
46+
return arr[pivot]
47+
48+
def pivoting(arr, left, right):
49+
# O(N) pivoting
50+
# takes the last element as pivot
51+
pivot = right
52+
new_pivot = left
53+
54+
# iterate the whole array (without the last element)
55+
# and put all elements smaller than the pivot (last element) in the first K spots
56+
# with the new_pivot we're "counting" how many smaller elements are there
57+
for j in range(left, right):
58+
if arr[j] < arr[pivot]:
59+
swap(arr, new_pivot, j)
60+
new_pivot += 1
61+
62+
# swap the last (pivot) element with the new_pivot position
63+
swap(arr, new_pivot, pivot)
64+
65+
# return the new pivot
66+
return new_pivot
67+
68+
def swap(arr, i, j):
69+
# swaps two elements in an array
70+
temp = arr[i]
71+
arr[i] = arr[j]
72+
arr[j] = temp
73+
74+
75+
##############
76+
# Solution 2 #
77+
##############
78+
79+
def find_kth_smallest(arr, k):
80+
n = len(arr)
81+
if k > n:
82+
return None
83+
if k < 1:
84+
return None
85+
86+
k -= 1
87+
left = 0
88+
right = n - 1
89+
90+
while True:
91+
pivot = pivoting(arr, left, right) # the same method from the previous solution
92+
93+
if pivot > k:
94+
right = pivot - 1
95+
elif pivot < k:
96+
left = pivot + 1
97+
else:
98+
return arr[pivot]
99+
100+
# not possible
101+
return None
102+
103+
104+
###########
105+
# Testing #
106+
###########
107+
108+
# Test 1
109+
# Correct result => 1 1 1 1 1 1
110+
arr = [1, 1, 1, 1, 1, 1]
111+
print([find_kth_smallest_recursive(arr, i) for i in range(1, len(arr) + 1)])
112+
print([find_kth_smallest(arr, i) for i in range(1, len(arr) + 1)])
113+
114+
# Test 2
115+
# Correct result => 0 1 2 4 4 4 6 8 8 10 11 12
116+
arr = [6, 4, 2, 12, 4, 8, 10, 1, 11, 0, 8, 4]
117+
print([find_kth_smallest_recursive(arr, i) for i in range(1, len(arr) + 1)])
118+
print([find_kth_smallest(arr, i) for i in range(1, len(arr) + 1)])
119+
120+
# Test 3
121+
# Correct result => 1 2 3 4 5
122+
arr = [5, 4, 3, 2, 1]
123+
print([find_kth_smallest_recursive(arr, i) for i in range(1, len(arr) + 1)])
124+
print([find_kth_smallest(arr, i) for i in range(1, len(arr) + 1)])

‎Lists/nth_smallest.py‎

Lines changed: 0 additions & 92 deletions
This file was deleted.

0 commit comments

Comments
 (0)