一个面试算法题

Question

有n个正整数，数值区间在（0，m），编码找出这n个数中最大的k个数，要求时间复杂度为O(m+n),
算法学的烂。。不知道怎么写阿 ， 求大牛~~

Answer 1

先排序，将排好序的数，放到数组a[]中，数组下标：0-（n-1），取啊a[0]到a[k-1]

Answer 2

建个数组a[m],然后遍历n个数，然后将数组中相应下标的值设为1，如这个整数为3，则a[3]=1，这样一次的复杂度为o(n)
然后由大到小遍历a[m]，取到前面为1的k值，最差的情况是0(m)
二者相加的复杂度为o(m+n)

Answer 3

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;
    }
}

Answer 4

重复？

for (int i = 0; i < n; i++) {
  a[b[i]]++;
}

其他的就不用说了吧

Answer 5

谢谢解答。。
郁闷， 想到这儿了就是又回去了 ，脑子真不好使。
那请问 如果n个数中有重复情况那么这方法应该时间复杂度不能达到O(m+n)吧。。

Answer 6

谢谢，不过出现这种情况 时间复杂度就要稍大于 O (m+n) 了吧 。

Answer 7

    public static void main(String[] args) {
        int nl = 100;
        int[] n = new int[nl];
        for (int i = 0; i < nl; i++) {
            n[i] = i + 1;
        }
        
        sf(n,1000,10);
    }
    //m+2n,也就是m+n了
    static void sf(int[]temp,int m,int k){
        byte[] counts = new byte[m+1];
        //n
        for (int i = 0; i < temp.length; i++) {
            counts[temp[i]+1]++;
        }
        //m+n
        for (int i = counts.length-1, count = 0; count < k && i > -1; i--) {
            if(counts[i]>0){
                System.out.print(i);
                System.out.print(",");
                counts[i]--;
                i++;
                count++;
            }
        }
    }

Answer 8

就本题来说，用计数排序是效率最高的(时间/空间复杂度：O(m+n) ):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];
        }
    }