[offer-29] The smallest number of K in 2010 814/02

[offer-29] The smallest number of K

  • Test Point: Advanced Array Algorithms
  • Time limit: 1 second
  • Space limitation: 32768K
  • Enter n integers and find out the smallest number of K. For example, the smallest four digits are 1,2,3,4 if you input 8 digits, 4,5,1,6,2,7,3,8.
Ideas:

Seeing this, I thought I would use the sorting algorithm, and then take out the first k directly. I reviewed the quick sorting again.

Code:
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (k > input.length) {
            return list;
        }
        QuickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
    public void QuickSort(int[] array, int low, int high) {
        if (low < high) {
            int index = getIndex(array, low, high);
            QuickSort(array, low, index - 1);
            QuickSort(array, index + 1, high);
        }
    }
    public int getIndex(int[] array, int low, int high) {
        int pivot = array[low];
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = pivot;
        return low;
    }
}
My question:
  1. Initially, the total number of arrays crossed the bounds. Because I didn't judge low < high in QuickSort function.
  2. Not considering that if K is larger than the length of the array, there is no such minimum number of k, so you should return to the empty ArrayList at this time.
Other ideas 1:

The idea of bubble sorting is only the outermost cycle K times, that is to say, without all sorting, only select the K that meets the purpose of the question.
This method is to put the smallest number at the end, and then take the array from the back.
But the time complexity will be high.
[Who would have thought that I always had the wrong answer because subscripts were added to list.add instead of array elements.] ____________ ]

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        // Bubble sort, only the first k
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (k > input.length || k == 0) {
            return list;
        }
         
        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;
                }
            }
            list.add(input[input.length - i - 1]);
        }
        return list;
    }
}

Other ideas 2:

In fact, I think the test point of this question should be heap sorting.

  • Create arrays of size k and design arrays to be the largest heap based on the principle of heap sorting.
  • Since the first k digits are found, which are relatively small, it is suitable to use small heel heap to solve the problem.
  • Because the big root heap gets the maximum value first, the time complexity can not reach the ideal nlogk.
  • The whole process operates on arrays, but it's the same as operating on a binary tree, because binary heaps can be represented by arrays.
  • The first element of the array is the root of the binary heap.
  • If we want to make sure it's the smallest heap, then the number we get from root must be the smallest.
  • After the root is extracted, the nature of the heap maintenance heap needs to be readjusted after the root and the last number are exchanged.
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (k > input.length || k == 0) {
            return list;
        }
        
        // Keep the smallest number of k
        int[] numbers = new int [k];
        for (int i = 0; i < k; i++) {
            numbers[i] = input[i]; // First put in the number of first k
        }
        
        for (int i = k / 2 - 1; i >= 0; i--) {
            adjustHeap(numbers, i, k - 1); // Construct arrays into maximum heap form
        }
        for (int i = k; i < input.length; i++) {
            if (input[i] < numbers[0]) {
                numbers[0] = input[i];
                adjustHeap(numbers, 0, k - 1); // Rearrangement of maximum heap
            }
        }
        for (int n : numbers) {
            list.add(n);
        }
        return list;
    }
    // Maximum heap adjustment method
    public void adjustHeap(int[] arr, int start, int end) {
        int temp = arr[start];
        int child = start * 2 + 1; // i's left child node number
        while (child <= end) {
            if (child + 1 <= end && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[child] < temp)
                break;
            arr[start] = arr[child];
            start = child;
            child = child * 2 + 1;
        }
        arr[start] = temp;
    }
}


Tags: Java

Posted on Mon, 02 Sep 2019 01:17:34 -0700 by eatadi