Description

Find the kth smallest numbers in an unsorted integer array.

Have you met this question in a real interview?

Yes

Example

Given[3, 4, 1, 2, 5], k =3, the 3rd smallest numbers are[1, 2, 3].

Challenge

An O(nlogn) algorithm is acceptable, if you can do it in O(n), that would be great.

class Solution {

public:

/\*

 \* @param k an integer

 \* @param nums an integer array

 \* @return kth smallest element

 \*/

int kthSmallest\(int k, vector<int> nums\) {

    // write your code here

    int start = 0, end = nums.size\(\) - 1;

    while \(true\) {

        if \(start > end\) {

            break;

        }

        int i = start, j = start, l = end + 1;

        int pivot = nums\[start + \(end - start >> 1\)\];

        while \(i < l\) {

            if \(nums\[i\] < pivot\) {

                swap\(nums\[i++\], nums\[j++\]\);

            } else if \(nums\[i\] == pivot\) {

                ++i;

            } else {

                swap\(nums\[i\], nums\[--l\]\);

            }

        }

        if \(k - 1 < j\) {

            end = j - 1;

        } else if \(k - 1 >= l\) {

            start = l;

        } else {

            return pivot;    

        }

    }

    return -1;

}

};

results matching ""

    No results matching ""