Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) on average using quickselect's side effects solution in Speedy category for Shorter Set by juestr
def remove_min_max(data: set, total:int) -> set:
# the next 4 functions are taken from median
def swap(i, j):
data[i], data[j] = data[j], data[i]
def reorder(i, j):
if data[j] < data[i]:
swap(i, j)
def partition_mo3_3way(left, right):
mid = (left + right) // 2
reorder(left, mid)
reorder(left, right)
reorder(right, mid)
pivot = data[right]
i, j, p = left, left, right
while i < p:
if data[i] < pivot:
swap(i, j)
i += 1
j += 1
elif data[i] == pivot:
p -= 1
swap(i, p)
else:
i += 1
l = min(p - j, right - p + 1)
swap(slice(j, j + l), slice(right - l + 1, right + 1))
return j, j + right - p
def quickselect(k, left=0, right=len(data) - 1):
while True:
if left == right:
return data[left]
pivot_l, pivot_r = partition_mo3_3way(left, right)
if pivot_l <= k <= pivot_r:
return data[k]
elif k < pivot_l:
right = pivot_l - 1
else:
left = pivot_r + 1
if len(data) - 2*total <= 0:
return set()
else:
data = list(data)
start, stop = total, len(data) - total
quickselect(start)
quickselect(stop, left=start+1)
return set(data[start:stop])
Nov. 10, 2021
Comments:
