有效地找到数组中第k个最小元素的索引(迭代)

Question

我想找到数组中第k个最小的元素，但实际上需要它的索引为我的分区方法。

我在这个博客上找到了这段代码，用于查找第k个最小元素:http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html

但是这只返回值，而不是索引。

你知道我怎样才能有效地找到它的索引吗?

Answer 1

最简单的方法是创建一个相同长度的额外的indices数组，用0到length-1的数字填充它，当arr数组更改时，与indices数组执行相同的更改。最后从indices数组返回相应的条目。你甚至不需要理解原始算法。下面是修改后的方法(我的更改用***标记):

public static int selectKthIndex(int[] arr, int k) {
    if (arr == null || arr.length <= k)
        throw new IllegalArgumentException();
    int from = 0, to = arr.length - 1;
    // ***ADDED: create and fill indices array
    int[] indices = new int[arr.length];
    for (int i = 0; i < indices.length; i++)
        indices[i] = i;
    // if from == to we reached the kth element
    while (from < to) {
        int r = from, w = to;
        int mid = arr[(r + w) / 2];
        // stop if the reader and writer meets
        while (r < w) {
            if (arr[r] >= mid) { // put the large values at the end
                int tmp = arr[w];
                arr[w] = arr[r];
                arr[r] = tmp;
                // *** ADDED: here's the only place where arr is changed
                // change indices array in the same way
                tmp = indices[w];
                indices[w] = indices[r];
                indices[r] = tmp;
                w--;
            } else { // the value is smaller than the pivot, skip
                r++;
            }
        }
        // if we stepped up (r++) we need to step one down
        if (arr[r] > mid)
            r--;
        // the r pointer is on the end of the first k elements
        if (k <= r) {
            to = r;
        } else {
            from = r + 1;
        }
    }
    // *** CHANGED: return indices[k] instead of arr[k]
    return indices[k];
}

注意这个方法修改了原来的arr数组。如果不喜欢这样，可以在方法的开头添加arr = arr.clone()。