weixin_52060533
weixin_52060533
2020-12-15 21:12
采纳率: 50%
浏览 124

求大神帮忙解决找第k名的问题,感激不尽!

                                                                                            c语言

找第k名 (10分)

整数数组中存储有N个整数,编写函数,找出并返回第k大的数。要求时间复杂度要优于O(NlogN)。题目确保输入的K是合法的(1<=k<=N)。你可以认为k远小于N。

函数接口定义:

6 3
(d[]={13,48,43,96,96,8},N=6,k=3)

其中 d ,N和 k 都是用户传入的参数。 d 是数组的初地址, N 是数组的长度, k 是名次,返回第k大的整数(最大值是第一)。

输入样例:

例如:

6 3
(d[]={13,48,43,96,96,8},N=6,k=3)

输出样例:

例如:

48
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • jslang
    天际的海浪 2020-12-16 00:08
    已采纳
    #include <stdio.h>
    
    int tk(int d[], int n,int k) {
    	int arr[k];
    	int len = 0;
    	int temp;
    	int ci;
    	int pi;
    	for (int i = 0; i < n; i++) {
    		if (len<k || d[i]>=arr[0]) {
    			if (len==k) {
    				len--;
    		 		temp = arr[len];
    		 		pi = 0;
    	 			ci = 1;
    				while (ci < len) {
    					if (ci+1 < len && arr[ci+1] < arr[ci])
    						ci++;
    					if (temp <= arr[ci])
      						break;
    					arr[pi] = arr[ci];
    					pi = ci;
    					ci = pi*2+1;
    				}
    				arr[pi] = temp;
    			}
    			len++;
    	 		ci = len-1;
    	 		pi = (ci-1)/2;
    	 		temp = d[i];
    			while (ci>0 && temp < arr[pi]) {
    				arr[ci] = arr[pi];
    				ci = pi;
    				pi = (ci-1)/2;
    			}
    			arr[ci] = temp;
    		}
    	}
    	return arr[0];
    }
    
    int main() {
        int n=6,k=3;
        int d[] = {13,48,43,96,96,8};
    	printf("%d",tk(d,n,k));
    	return 0;
    }
    
    点赞 评论
  • jslang
    天际的海浪 2020-12-15 22:20
    点赞 评论
  • jslang
    天际的海浪 2020-12-16 00:04
    #include <stdio.h>
    
    int tk(int d[], int n,int k) {
    	int arr[k];
    	int len = 0;
        int temp;
        int ci;
        int pi;
    	for (int i = 0; i < n; i++) {
    		if (len<k || d[i]>=arr[0]) {
    			if (len==k) {
    			    len--;
    		 	    temp = arr[len];
    		 	    pi = 0;
    	 			ci = 1;
    		        while (ci < len) {
    			        if (ci+1 < len && arr[ci+1] < arr[ci])
    			        	ci++;
    		            if (temp <= arr[ci])
      			            break;
                        arr[pi] = arr[ci];
                        pi = ci;
                        ci = pi*2+1;
    		        }
                    arr[pi] = temp;
    			}
    		    len++;
    	 	    ci = len-1;
    	 	    pi = (ci-1)/2;
    	 	    temp = d[i];
    	        while (ci>0 && temp < arr[pi]) {
    	            arr[ci] = arr[pi];
    	            ci = pi;
    	            pi = (ci-1)/2;
    	        }
    	        arr[ci] = temp;
    		}
    	}
    	return arr[0];
    }
    
    int main() {
        int n=10,k=5;
        int d[] = {13,8,47,36,96,96,67,8,54,4};
        printf("%d",tk(d,n,k));
        return 0;
    }
    
    点赞 评论
  • weixin_52060533
    weixin_52060533 2020-12-16 12:13

    不对啊,兄弟

    点赞 评论

相关推荐