HOME/剑指Offer/

1.题目描述

Article Outline
TOC
Collection Outline

1.题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

2.解析

2.1冒泡排序

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
          ArrayList<Integer> al = new ArrayList<Integer>();
           if(k > input.length){
               return al;
           }
            for(int i = 0; i < k; i++){
                for(int j = 0;j<input.length-i-1;j++){
                if (input[j] < input[j + 1]) {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                } 
                }
             al.add(input[input.length - i - 1]);
            }
        return al;
    }
}

2.2JAVA类库

import java.util.*;
//时间复杂度为 nlogN
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || k <= 0 || k > input.length) {
            return res;
        }
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }
}

2.3快排的partition函数

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (input == null || input.length == 0 || input.length < k || k == 0) {
            return new ArrayList<>();
        }
        // 在数组中寻找位置为k - 1的pivot
        int start = 0, end = input.length - 1;
        int index = partition(input, start, end);
        while (index != k - 1) {
            if (index < k - 1) {
                start = index + 1;
            } else {
                end = index - 1;
            }
            index = partition(input, start, end);
        }

        // 收集这k个数
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i <= index; i++) {
            res.add(input[i]);
        }
        return res;
    }

        public static int partition(int[] arr, int lo, int hi) {
        // random swap reduce rate of baddest case appear 
        swap(arr, lo + (int) Math.random() * (hi - lo + 1), hi);
        // divide orginal array to smaller and equal or bigger two part
        int small = lo - 1;
        while (lo < hi) {
            if (arr[lo] < arr[hi]) {
                swap(arr, ++small, lo++);
            } else {
                lo++;
            }
        }
        // put pivot into middle
        swap(arr, ++small, hi);

        // return middle position
        return small;
    } 

        // swap array element in i and j
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

2.4最优解

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (input == null || input.length == 0 || input.length < k || k == 0) {
            return new ArrayList<>();
        }
        // make a big root heap size of k
        // traverse input 
        // when heap is full and heap's top is bigger than current element
        // use current element replace heap's top
        PriorityQueue<Integer> bigHeap = new PriorityQueue<>(new MyComparator());
        for (int num : input) {
            if (bigHeap.size() < k) {
                bigHeap.add(num);
            } else {
                if (num < bigHeap.peek()) {
                    bigHeap.poll();
                    bigHeap.add(num);
                }
            }
        }

        // collect all k elements
        ArrayList<Integer> res = new ArrayList<>();
        while (!bigHeap.isEmpty()) {
            res.add(bigHeap.poll());
        }
        return res;
    }

    // big root heap comparator
    class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }

    }
}