Small element K] [LeetCode disorderly array | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This topic is question 12. I have to say the nuggets theme is beautiful! Praise.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

Unordered array K element

Description finding the KTH smallest number in an unordered array

Sample 1:

Input: [3, 4, 1, 2, 5], k = 3 Output: 3Copy the code

Example 2:

Input: [1, 1, 1], k = 2 Output: 1Copy the code

It’s ok to challenge the O(nlogn) algorithm, but if you can solve it O(n), that’s great.

Ii. Analysis of Ideas:

The simplest is to sort directly, select the value of the KTH position, the time complexity is O(nlog)O(nlog)O(nlog); The recommended double pointer + quicksort template is used here

methods	describe	Time complexity	Spatial complexity
Double pointer method (likeness)	I’m just using two Pointers, double Pointers, and the idea is to use quicksort	$O(n)$	$(1)$

Partition steps:

1. makeleft = start.right = end.pivot = nums[left].
2. whennums[left] < pivotWhen,leftThe pointer moved to the right.
3. whennums[right] > pivotWhen,rightThe pointer moves to the left.
4. Swap the values of the two positions,rightThe pointer moves to the left,leftMove the pointer to the right.
5. Return to step 2 until the two Pointers meet.

After each partition, search for the next search range according to the pivot position.

Iii. AC Code:

public class Solution {
    / * * *@param k: An integer
     * @param nums: An integer array
     * @return: kth smallest element
     */
    public int kthSmallest(int k, int[] nums) {
         return quickSelect(nums, 0, nums.length - 1, k - 1);
    }

    / * * * *@param nums
     * @param i
     * @param j
     * @param k
     * @return* /
    private int quickSelect(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];

        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }

            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                inttemp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; }}// conditions
        if (right >= k && right >= start) {
            return quickSelect(nums, start, right, k);
        } else if (left <= k && left <= end) {
            return quickSelect(nums, left, end, k);
        }
        returnnums[k]; }}Copy the code

Iv. Summary:

This problem can be classified as a double pointer algorithm type of problem, can also be classified as a partition algorithm class of problem, can be matched with the 11th problem to eat better!

• Form is a variant of the double pointer, used inleft,right,pivotThree Pointers
• This is actually a variation of the quicksort algorithm, by the quicksort algorithmpartitionThe steps can be less thanpivotIs divided by the value ofOn the left side of the pivot, is more thanpivotIs divided by the value ofpivotThe right-hand side, so I can get it directlypivotThe scope of. So we can narrow it down to number onekLarger value.