Python finds the minimum number of K instance codes

Topic describes

Enter n integers and find the smallest NUMBER of K. For example, if you input 4,5,1,6,2,7,3,8, then the four smallest Numbers are 1,2,3,4.

There are many ways to complete this problem. Many sorting algorithms can complete the established operation. The key is the consideration of complexity. The following ideas should serve as a starting point for the author. If readers are interested, they can try other methods.

Idea 1: Use bubble method

Adjacent Numbers are compared in pairs and swapped from smallest to largest, or if the first value is larger than the last, then swapped. After 1 trip, the smallest number is switched to the first digit; And then the second smallest switch to the second... , until the k number, stop the exchange. Returns the number of k before lists (lists[0:k], closed before open)

Idea 2: Use the partition idea from quicksort.

We set the sentry of partition function as key=lists[left]. The result of completing 1 round of comparison in partition function is that the number larger than key is on its right side, and the number smaller than key is on its left side. Returns the value of left when left=right after completing the round.

We judge whether the value of left is larger or smaller than that of k:

If the value of left is larger than that of k, it means that after the last round of partition, the first left in lists is smaller on the left and the rest on the right. We also need to narrow down the search range, and next time we will only find the left number in front of the array.

If the value of left is smaller than k, the previous left number after partition is too small, we need to look further back in the array.

# -*- coding: utf-8 -*- 
""" 
Date: Tue Sep 19 10:50:11 2017 
 
Created by @author: xiaoguibao 
 
E-mail: mingliumengshao@163.com 
 
Content:  Looking for the smallest k The number of  
 
""" 
def function1(lists,k): 
#   The bubbling method  
  length = len(lists) 
  for i in range(k): 
    for j in range(i+1,length): 
      if lists[i] > lists[j]: 
        lists[j],lists[i] = lists[i],lists[j] 
  return lists[0:k] 
 
""" 
 Train of thought 2  including 2 A part of function2_partion and function2 
""" 
 
def function2_partion(lists,left,right): 
  # Divide the processing part of the function  
  key = lists[left] 
  while left < right: 
    while left < right and lists[right] >= key: 
      right -= 1 
    lists[left] = lists[right] 
    while left < right and lists[left] <= key: 
      left += 1 
    lists[right] = lists[left] 
  lists[right] = key 
  return left 
def function2(lists,k): 
  # The main functional part of partition  
  length = len(lists) 
  left = 0 
  right = length - 1 
  index = function2_partion(lists,left,right) 
  while k!=index: 
    if index > k-1: 
      right = index-1 
    else: 
      left = index+1 
    index = function2_partion(lists,left,right)  
  return lists[0:k] 
 
def main(): 
  lists = [1,1,6,4,11,9,2,10,3] 
#  print " Train of thought 1( The bubbling method ):",function1(lists,8) 
  print " Train of thought 2( Classification method ):",function2(lists,8) 
if __name__=="__main__": 
  main() 

conclusion

That's it for Python to find the smallest number of K instance code. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!