forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
k-th-smallest-prime-fraction.py
40 lines (37 loc) · 1.07 KB
/
k-th-smallest-prime-fraction.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
# Time: O(nlogr)
# Space: O(1)
class Solution(object):
def kthSmallestPrimeFraction(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: List[int]
"""
def check(mid, A, K, result):
tmp = [0]*2
count = 0
j = 0
for i in xrange(len(A)):
while j < len(A):
if i < j and A[i] < A[j]*mid:
if tmp[0] == 0 or \
tmp[0]*A[j] < tmp[1]*A[i]:
tmp[0] = A[i]
tmp[1] = A[j]
break
j += 1
count += len(A)-j
if count == K:
result[:] = tmp
return count >= K
result = []
left, right = 0.0, 1.0
while right-left > 1e-8:
mid = left + (right-left) / 2.0
if check(mid, A, K, result):
right = mid
else:
left = mid
if result:
break
return result