This is the 9th day of my participation in Gwen Challenge

Minimum number of K (Interview question 17.14)

Topic describes

Design an algorithm to find the smallest k number in an array. You can return these k numbers in any order.

Example 1:

Arr = [1,3,5,7,2,4,6,8], k = 4 output: [1,2,3,4]Copy the code

prompt

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

Thought analysis

The simplest and most crude way to find the minimum number of K is to sort the array and find the minimum number of K directly. For example, if we use quicksort, the time complexity is O(nlogn){O(nlogn)}O(nlogn), but we can further optimize it by using the idea of quicksort, which uses the idea of divide and conquer, Take a value that is greater than the value on the left and less than the value on the right. Finding the smallest K number can be transformed into finding the (length-k) largest number first.

After each quicksort, we can shrink our interval, because we don’t have to sort the array, only need to find the smallest part of the value, so the final time complexity is O(n){O(n)}O(n).

The code shown

Solution 1: Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

public int[] smallestK(int[] arr, int k) {
        if (arr.length == 0) {return arr;
        }

        int m = arr.length  - k;
        int start = quickSort(arr,m);
        int[] nums = new int[k];
        int index = 0;
        for (inti = m; i < arr.length; i++){ nums[index++] = arr[i]; }return nums;
    }

    private int quickSort(int[] nums,int k){
        return quickInternal(nums,0,nums.length - 1,k);
    }

    private int quickInternal(int[] nums,int left,int right,int k){  / / 5,4,3,2,2,2,1,0
        int division = division(nums, left, right);
        if (division + 1 == k){
            return division;
        } else if(division + 1 > k){
            return quickInternal(nums,left,division - 1,k);
        } else {
            return quickInternal(nums,division + 1,right,k); }}private int division(int[] nums,int left,int right){
        int base = nums[left];
        while (left < right){
            while (left < right && nums[right] <= base){
                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] > base){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = base;
        return left;
    }
Copy the code

The KTH largest element in the array (215)

Topic describes

Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.

Advanced:

  • You can be inO(n log n)Sorting linked lists in time complexity and constant space complexity?

Example 1:

Input: [3,2,1,5,6,4] and k = 2 output: 5Copy the code

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4Copy the code

instructions

You can assume that k is always valid, and that 1 ≤ k ≤ the length of the array.

Thought analysis

The simplest and most crude way to find the KTH largest element in an array is to sort the array and then directly find the KTH largest element. For example, if we use quicksort, the time is O(nlogn){O(nlogn)}O(nlogn), But we can optimize it further by using the idea of quicksort, which is the idea of divide-and-conquer, where you take a value that’s greater than that value on the left and less than that value on the right.

After each quicksort, we can shrink our interval, because we don’t have to sort the array, only need to find the smallest part of the value, so the final time complexity is O(n){O(n)}O(n).

The code shown

Solution 1: Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,k);
    }

    private int quickSort(int[] nums,int k){  / / 3, 2, 1
        return quickInternal(nums, 0, nums.length - 1,k);
    }

    private int quickInternal(int[] nums,int left,int right,int k){
        int division = division(nums,left,right); / / 5,4,3,2,1 5
        if (division+1 == k){
            return nums[division];
        } else if (division+1 > k){
            return quickInternal(nums,left,division-1,k);
        } else {
            return quickInternal(nums,division+1,right,k); }}private int division(int[] nums,int left,int right){
        int base = nums[left];
        while (left < right){
            while (left < right && nums[right] <= base){
                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] > base){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = base;
        return left;
    }
Copy the code

conclusion

For the KTH large/small element and the maximum/small number of K, the solution idea is the same, using the idea of quick sorting, without specific detailed sorting, the time complexity is O(n){O(n)}O(n), the space complexity is O(1){O(1)}O(1).