有n个正整数，数值区间在（0，m），编码找出这n个数中最大的k个数，要求时间复杂度为O(m+n),。。。
算法学的烂。。不知道怎么写阿 ， 求大牛~~
------解决方案--------------------
建个数组a[m],然后遍历n个数，然后将数组中相应下标的值设为1，如这个整数为3，则a[3]=1，这样一次的复杂度为o(n)
然后由大到小遍历a[m]，取到前面为1的k值，最差的情况是0(m)
二者相加的复杂度为o(m+n)
------解决方案--------------------
int a[] = new int[m];
int b[] = new int[n];
int c[] = new int[k];
for (int i = 0; i < n; i++) {
a[b[i]] = 1;
}
int count = 0;
for (int i = m - 1; i >= 0; i++) {
if (a[i] == 1) {
c[count] = i;
count++;
}
if (count == k) {
break;
}
}
------解决方案--------------------
------解决方案--------------------
就本题来说，用计数排序是效率最高的(时间/空间复杂度：O(m+n) ):
- Java code
public static void main(String[] args) { int[] data = new int[] { 2，10，11,4，21,5,7,6,19，15 }; bucketSort(data, 2, 22); } /** * 排序方法 * * @param data * 待排序数组 * @param min * 待排序数组最小边界值 * @param max * 待排序数组最大边界值+1 * @return 无 */ public static void bucketSort(int[] data, int min, int max) { int[] tmp = new int[data.length];// 1.创建缓存数组;再对于这个可枚举范围构建一个buckets数组(定义max-min个桶) int[] buckets = new int[max - min]; // 2.计算每个元素在序列出现的次数 for (int i = 0; i < data.length; i++) { buckets[data[i] - min]++; } // 3.计算"落入"各桶内的元素在有序序列中的位置 for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } // 4.将data中的元素完全复制到tmp数组中 System.arraycopy(data, 0, tmp, 0, data.length); // 5.根据buckets数组中的信息将待排序列的各元素放入相应位置 for (int k = data.length - 1; k >= 0; k--) {// 倒序循环为的是稳定性 data[--buckets[tmp[k] - min]] = tmp[k]; } }