Java: 快速从一堆数据中找出第n大值的id

今天在写程序的时候遇到这样一个问题:要从一堆double型的数据中找出第n大的那个。以前也遇到过,图省事直接sort一下再直接拿第n个数据。Java里面的Collections.sort()方法其实已经很快了。不过,找一个值就去把整个List都sort了,我还是觉得有点太弱智了。

还是自己写一个吧。程序相当简单,也没啥好说明的,有问题参考下Quicksort。

需要说明的一点是,我这里rank是从0开始的。所以如果要找第三大的值,rank应该是2。
本程序在Java 1.7版本下调试通过。

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;

public class Test {
	public static int getIdByRank(List<Double> data, List<Integer> idx, int rank) {
		System.out.println("Current heap...for " + rank);
		for (int i = 0; i < idx.size(); i++) {
			System.out.println("  " + idx.get(i) + ": " + data.get(idx.get(i)));
		}
		if (rank == 0 && idx.size() == 1) {
			return idx.get(0);
		}
		List<Integer> idl = new ArrayList<Integer>(); // left list
		List<Integer> idr = new ArrayList<Integer>(); // right list
		double value = data.get(idx.get(0));

		for (int i = 1; i < idx.size(); i++) {
			if (data.get(idx.get(i)) > value) {
				idl.add(idx.get(i));
			} else {
				idr.add(idx.get(i));
			}
		}

		System.out.println("  First Half (" + idl.size()+ ")");
		for (int i = 0; i < idl.size(); i++) {
			System.out.println("  " + idl.get(i) + ": " + data.get(idl.get(i)));
		}
		System.out.println("  Second Half (" + idr.size()+")");
		for (int i = 0; i < idr.size(); i++) {
			System.out.println("  " + idr.get(i) + ": " + data.get(idr.get(i)));
		}

		System.out.println("  Rank of pivot: " + idl.size());
		if (idl.size() == rank) {
			return idx.get(0);
		}

		if (idl.size() > rank) {
			return getIdByRank(data, idl, rank);
		} else {
			return getIdByRank(data, idr, rank - idl.size() - 1);
		}
	}

	public static void main(String[] args) {
		List<Double> data = new ArrayList<Double>();
		List<Integer> ids = new ArrayList<Integer>();

		SecureRandom sr = new SecureRandom();

		for(int i=0; i<5; i++) {
			ids.add(i);
			data.add(sr.nextDouble());
		}

		int rank = 3;
		System.out.println("The Id of Rank " + rank + " data is " + getIdByRank(data, ids, rank));
	}
}

运行结果

Current heap...for 3
  0: 0.39587504781146243
  1: 0.9049711778430899
  2: 0.8995269363777996
  3: 0.20384806961801805
  4: 0.1299586319149758
  First Half (2)
  1: 0.9049711778430899
  2: 0.8995269363777996
  Second Half (2)
  3: 0.20384806961801805
  4: 0.1299586319149758
  Rank of pivot: 2
Current heap...for 0
  3: 0.20384806961801805
  4: 0.1299586319149758
  First Half (0)
  Second Half (1)
  4: 0.1299586319149758
  Rank of pivot: 0
The Id of Rank 3 data is 3

原创文章,转载请注明: 转载自 iDEAnels

本文地址: Java: 快速从一堆数据中找出第n大值的id

Leave a Reply

Your email address will not be published. Required fields are marked *