BFPRT algorithm - Median of medians

O(n) running time
a selection algorithm based on the quickselect algorithm

having worst-case linear time complexity for selecting the kth largest element

题目

给定一个无序的整型数组arr，找到其中最小的k个数。

如果数组arr的长度为N，排序之后自然可以得到最小的k个数，此时时间复杂度为排序的时间复杂度即O(NlogN)
本题要求读者实现时间复杂度O(NlogK)和O(N)的方法

思路

快排也能做，但是由于是随机的选择k，因此只能O(N*logN)

BFPRT

时间复杂度O(N)
其精髓是选择pivot，不是任意的选,
而是选择中位数中的中位数-Median of medians

步骤：

  1. 5个数分一组，分为n/5一组
  2. 组内插入排序，选择所有的上中位数，单独组成一个数组arrm[]
  3. 求所有中位数的中位数，即arrm[]的中位数，使用递归调用，求出次中位数pivot
  4. 然后快排使用pivot来划分区域，看k是否是中间区域

堆排序

时间复杂度O(N*logK)
不需要所有的都排序，因此比快排好，更加适合从一堆选前k个大的

步骤:

  1. 建k长度的堆
  2. 然后对于数组里的剩余数字，每次替换堆顶，
    对于大于当前堆顶的数字，不用替换，因为他不可能是前k大的数字
  3. 每次替换后调整结构，保证堆的定义

代码

BFPRT

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//得到0-k大的数组
public int[] getMinKNumsByBFPRT(int[] arr, int k) {
	if (k < 1 || k > arr.length) {
		return arr;
	}
	int minKth = getMinKthByBFPRT(arr, k);
	int[] res = new int[k];
	int index = 0;
	for (int i = 0; i != arr.length; i++) {
		if (arr[i] < minKth) {
			res[index++] = arr[i];
		}
	}
	for (; index != res.length; index++) {
		res[index] = minKth;
	}
	return res;
}
//得到第k个大的数字
public int getMinKthByBFPRT(int[] arr, int K) {
	int[] copyArr = copyArray(arr);
	return select(copyArr, 0, copyArr.length - 1, K - 1);
}
public int[] copyArray(int[] arr) {
	int[] res = new int[arr.length];
	for (int i = 0; i != res.length; i++) {
		res[i] = arr[i];
	}
	return res;
}
//返回值是int，选择i位置的数字，返回结果
public int select(int[] arr, int begin, int end, int i) {
	if (begin == end) {
		return arr[begin];
	}
	//选择中位数的中位数
	int pivot = medianOfMedians(arr, begin, end);
	//找到与pivot相等的数组下标
	int[] pivotRange = partition(arr, begin, end, pivot);
	if (i >= pivotRange[0] && i <= pivotRange[1]) {
		return arr[i];
	} else if (i < pivotRange[0]) {
		//如果没命中就去找比pivot小的中位数
		//pivotRange[0]是与pivot值相等的左边位置
		return select(arr, begin, pivotRange[0] - 1, i);
	} else {
		//pivotRange[1]是与pivot值相等的右边位置
		return select(arr, pivotRange[1] + 1, end, i);
	}
}
//找中位数的中位数
public int medianOfMedians(int[] arr, int begin, int end) {
	int num = end - begin + 1;
	//不是5的倍数，就要多一组
	int offset = num % 5 == 0 ? 0 : 1;
	int[] mArr = new int[num / 5 + offset];
	for (int i = 0; i < mArr.length; i++) {
		int beginI = begin + i * 5;
		int endI = beginI + 4;
		//mArr是中位数的集合
		mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
	}
	//选择中位数组中的中位数
	return select(mArr, 0, mArr.length - 1, mArr.length / 2);
}
/**
 * @param pivotValue 选择的中间位置
 * partition的目的是利用快排将arr进行分区
 * 左边比pivotValue小，右边比pivotValue大，中间是与pivotValue相等的
 * @return 返回值是int数组，返回的是与pivotValue相等的数组下标
 */
public int[] partition(int[] arr, int begin, int end, int pivotValue) {
	int small = begin - 1;
	int cur = begin;
	int big = end + 1;
	//快排原理，将arr分区，
	//左边是比pivotValue小的,右边比pivotValue大，中间的和pivotValue等
	while (cur != big) {
		if (arr[cur] < pivotValue) {
			swap(arr, ++small, cur++);
		} else if (arr[cur] > pivotValue) {
			swap(arr, cur, --big);
		} else {
			cur++;
		}
	}
	//得到与pivotValue相等的位置的坐标范围
	int[] range = new int[2];
	//最左边
	range[0] = small + 1;
	//最右边
	range[1] = big - 1;
	return range;
}
//得到中间位置的数字
public int getMedian(int[] arr, int begin, int end) {
	insertionSort(arr, begin, end);
	int sum = end + begin;
	int mid = (sum / 2) + (sum % 2);
	return arr[mid];
}
//插入排序
public void insertionSort(int[] arr, int begin, int end) {
	for (int i = begin + 1; i != end + 1; i++) {
		for (int j = i; j != begin; j--) {
			if (arr[j - 1] > arr[j]) {
				swap(arr, j - 1, j);
			} else {
				break;
			}
		}
	}
}
public void swap(int[] arr, int index1, int index2) {
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

Heap

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
public int[] getMinKNumsByHeap(int[] arr, int k) { 
    if (k < 1 || k > arr.length) { 
        return arr; 
    } 
    
    //建堆，长度为k，因为只需要找出前k大的数字
    int[] kHeap = new int[k]; 
    for (int i = 0; i != k; i++) {
    	//向堆中插入数字
        heapInsert(kHeap, arr[i], i); 
    } 
    
    //找出前k大的数字
    for (int i = k; i != arr.length; i++) { 
    	//kHeap[0]是当前第k大的数字
    	//因为只需要找前k大的数字，因此比堆顶大的数字不需要考虑，因为他至少是k+1大的数字了
        if (arr[i] < kHeap[0]) { 
        	//将当前堆顶换掉，换位目前第k大的数字
            kHeap[0] = arr[i]; 
            //调整堆，因为换了堆顶，要满足堆的定义
            heapify(kHeap, 0, k); 
        } 
    } 
    return kHeap; 
} 
public void heapInsert(int[] arr, int value, int index) { 
    arr[index] = value; 
    //保证是堆，即每个树父亲比孩子大
    while (index != 0) { 
        int parent = (index - 1) / 2;
        //父亲小，作调整，在循环里，保证交换后都可以符合堆的定义
        if (arr[parent] < arr[index]) { 
            swap(arr, parent, index); 
            index = parent; 
        } else { 
            break; 
        } 
    } 
} 
public void heapify(int[] arr, int index, int heapSize) { 
	//找到左右孩子
    int left = index * 2 + 1; 
    int right = index * 2 + 2; 
    //假设堆顶最大
    int largest = index; 
    //发现比堆顶大的就交换，循环里保证堆的定义
    while (left < heapSize) { 
    	
    	//2个if找到父亲，左右孩子中最大的值，然后交换
        if (arr[left] > arr[index]) { 
            largest = left; 
        } 
        if (right < heapSize && arr[right] > arr[largest]) { 
            largest = right; 
        }
        
        //交换
        if (largest != index) { 
            swap(arr, largest, index); 
        } else { 
            break; 
        }
        //使当前位置指向交换过的位置，继续检查
        index = largest; 
        left = index * 2 + 1; 
        right = index * 2 + 2; 
    } 
} 
public void swap(int[] arr, int index1, int index2) { 
    int tmp = arr[index1]; 
    arr[index1] = arr[index2]; 
    arr[index2] = tmp; 
}