分治法/第k小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package xcrj.kchalgorithm.divideConquer;

/**
 * 寻找序列中第k小元素
 * 利用快速排序
 * 快速排序：子序列左右比较定轴值索引，这个轴值索引就是第k-1小的
 * - 树形分区排序
 * - 递归分区内比较交换返回轴值索引
 * - 递归（根据轴值索引）进行左右分区划分》分区内左右索引对应值比较交换，索引相等时返回轴值索引
 * - 轴值左分区数值< 轴值 <轴值右分区数值
 */
public class KthMin {

    /**
     * 寻找序列中第k小元素
     *
     * @param r     输入数组
     * @param start 分区左边界
     * @param end   分区右边界 r.length-1
     * @param k     第k小的元素位于k-1索引处
     */
    public static int kthMin(int[] r, int start, int end, int k) {
        int pivot;
        if (start < end) {
            // 分区内比较交换获取轴值索引
            pivot = partition(r, start, end);
            if (pivot == k - 1) {
                return r[k - 1];
            }
            if (pivot > k - 1) {
                // 递归左分区
                return kthMin(r, start, pivot - 1, k);
            } else {
                // 递归右分区
                return kthMin(r, pivot + 1, end, k);
            }
        }

        if (start == end && start == k - 1) {
            return r[k - 1];
        }

        return -1;
    }

    /**
     * 分区内比较交换返回轴值索引
     *
     * @param start 分区左边界
     * @param end   分区右边界
     * @return 轴值索引
     */
    public static int partition(int[] r, int start, int end) {
        int left = start;
        int right = end;
        // 临时交换变量
        int temp;
        // 保证left<right
        while (left < right) {
            while (left < right && r[left] < r[right]) right--;
            if (left < right) {
                temp = r[right];
                r[right] = r[left];
                r[left] = temp;
                // r[left]和r[right]比较过了，不再比较
                left++;
            }
            while (left < right && r[left] < r[right]) left++;
            if (left < right) {
                temp = r[right];
                r[right] = r[left];
                r[left] = temp;
                // r[left]和r[right]比较过了，不再比较
                right--;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] inputs = {1, 2, 3, 10, 20, 20};
        int result = kthMin(inputs, 0, inputs.length - 1, 5);
        System.out.println(result);
    }
}