当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

一组N个数,确定其中抵第k个最大值

发表于: 2013-03-07   作者:暗蓝幽谷   来源:转载   浏览:
摘要: 首先,这个问题的最容易想到的就是冒泡排序。先把N个数存入数组中,之后 用冒泡算法从大到小排序,在取k位置的值。 具体求解过程如下: import java.util.Random; public class MaxK{ static int[] nums = new int[20]; static Random rand = new Random(4); pub

首先,这个问题的最容易想到的就是冒泡排序。先把N个数存入数组中,之后 用冒泡算法从大到小排序,在取k位置的值。

具体求解过程如下:

import java.util.Random;

public class MaxK{

	static int[] nums = new int[20];
	
	static Random rand = new Random(4);

	public static void main(String[] args){
		int k = Integer.parseInt(args[0]);
		init();
		printNums(nums);
		int[] sortBubble = bubbleSort(nums);
		printNums(sortBubble);
		
		System.out.println(sortBubble[k - 1]);
	}


	static void printNums(int[] nums){
		for(int i = 0, len = nums.length; i < len; i++)
			System.out.print(nums[i] + " ");
		System.out.println();
	}
	
	static void init(){
		for(int i = 0; i < 20; i++)
			nums[i] = rand.nextInt(100);
	}
	
	static int[] bubbleSort(int[] nums){
		int arrLen = nums.length;
		int[] bubble = new int[arrLen];	
		System.arraycopy(nums, 0, bubble, 0, arrLen);
		
		for(int i = 0; i < arrLen; i++){
			int tk = bubble[i];
			int tkj = i + 1;
			for(int j = i + 1; j < arrLen; j++){
				if(bubble[j] > tk){	
					tk = bubble[j];
					tkj = j;
				}
			}
			if(tk > bubble[i]){
				int temp = bubble[i];
				bubble[i] = bubble[tkj];
				bubble[tkj] = temp;
			}
		}
		
		return bubble;
	}
}

 还有稍微好一些的算法,就是先把前k个元素读入数组,再对其排序(递减)。接着逐个对比剩下的元素,将符合的元素插入k数组,调整k数组。

	static int maxK(int lk){// 求第lk大的数值
		int[] karr = new int[lk];
		System.arraycopy(nums, 0, karr, 0, lk);
		
		int[] bubbledKarr = bubbleSort(karr);
		int rek = bubbledKarr[lk - 1];
		
		for(int i = lk; i < 20; i++){ //20是nums长度,判断剩下的元素
			if(nums[i] > bubbledKarr[lk -1]){
				int loc = lk -2;
				for(; loc >=0 ; loc--)
					if(nums[i] < bubbledKarr[loc])
						break;
				loc++; //定位插入元素位置
				int[] temp = new int[lk - loc];//需要调整的k数组的值
				System.arraycopy(bubbledKarr, loc, temp, 0, lk - loc);
				bubbledKarr[loc] = nums[i];
				System.arraycopy(temp, 0, bubbledKarr, loc + 1, lk - loc -1);//调整替换元素之后的k数组
				
			}
		}

		return bubbledKarr[lk - 1];
	}

 

 

一组N个数,确定其中抵第k个最大值

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号