Google 不甘心的跪经

小A要当码农 发表于 2016-12-1 04:19
梁神 这个题的idea是不是先对原数组做partition,求得第K大的元素M，然后双指针，比M小的放数组左边，比M ...

嗯我感觉应该是用quick sort变体，比如在找数组的最后一个数，然后双指针遍历数组，找到比这个数小的数k1个，比这个数大的数k2个，如果k1等于(k - 1)，就找到了这个数，k1大于(k - 1)，在比这个数小的数里找第k个，k1大于(k - 1)，在比这个数大的数里找第(k - 1 - k1)个，应该和你的想法一样，毕竟庄神