## Solutions

# -*- coding:utf-8 -*-
class Solution:
def partition(self, arr, low, high):
pivot = arr[high]
i = low
for j in xrange(low, high):
if arr[j] <= pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quick_sort(self, arr, low=0, high=None):
if high is None:
high = len(arr) - 1

def _quicksort(arr, low, high):
if low >= high:
return
pivot = self.partition(arr, low, high)
_quicksort(arr, low, pivot-1)
_quicksort(arr, pivot+1, high)
return _quicksort(arr, low, high)

def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if tinput == [] or not tinput:
return []
if k > len(tinput) or k == 0:
return []
self.quick_sort(tinput)
res = []
pre = tinput[0]
res.append(pre)
for num in tinput:
if num != pre:
res.append(num)
pre = num
if len(res) == k:
break
return res


# -*- coding:utf-8 -*-
class Solution:
def partition(self, arr, low, high):
pivot = arr[high]
i = low
for j in xrange(low, high):
if arr[j] <= pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quick_sort(self, arr, low=0, high=None):
if high is None:
high = len(arr) - 1

def _quicksort(arr, low, high):
if low >= high:
return
pivot = self.partition(arr, low, high)
_quicksort(arr, low, pivot-1)
_quicksort(arr, pivot+1, high)
return _quicksort(arr, low, high)

def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if tinput == [] or not tinput:
return []
if k > len(tinput) or k == 0:
return []
low = 0
high = len(tinput) - 1
idx = self.partition(tinput, low, high)
while idx != k -1:
if idx > k - 1:
high = idx - 1
idx = self.partition(tinput, low, high)
else:
low = idx + 1
idx = self.partition(tinput, low, high)
res = tinput[:k]
self.quick_sort(res)
return res


# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
import heapq
if k > len(tinput):
return []
return heapq.nsmallest(k, tinput)