从Java Array获得前四大值
我试图从整数数组输入中找到前4个最大值。 例如，对于给定的输入数组{1232，-1221,0,345,78,99}将返回{1232,345,99,78}作为前4个最大值。 我用下面的方法解决了这个问题。 但我仍然不满足于它的时间效率。 当输入变大时，是否有机会更多地优化方法？ 任何线索都非常感谢。 谢谢。
public int[] findTopFourMax(int[] input) { int[] topFourList = { Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE }; for (int current : input) { if (current > topFourList[0]) { topFourList[3] = topFourList[2]; topFourList[2] = topFourList[1]; topFourList[1] = topFourList[0]; topFourList[0] = current; } else if (current > topFourList[1]) { topFourList[3] = topFourList[2]; topFourList[2] = topFourList[1]; topFourList[1] = current; } else if (current > topFourList[2]) { topFourList[3] = topFourList[2]; topFourList[2] = current; } else if (current > topFourList[3]) { topFourList[3] = current; } } return topFourList; }
最简单 （尽管不是最有效）的方法是对包含最后4个元素的子数组进行排序 。
您可以使用Arrays.sort()进行排序，使用Arrays.copyOfRange()来获取子Arrays.copyOfRange() 。
int[] arr = new int[] {1232, -1221, 0, 345, 78, 99}; Arrays.sort(arr); int[] top4 = Arrays.copyOfRange(arr, arr.length-4,arr.length); System.out.println(Arrays.toString(top4));
为了获得更有效的解决方案，可以维护前K个元素的最小堆或使用选择算法来查找前4个元素。 这个线程描述了这两种方法。
虽然选择算法提供O(n)解决方案，但是最小堆解决方案（ O(nlogK) ）应该具有更好的常量，特别是对于小k可能更快。
PS（编辑）：
对于4个元素，您可能会发现调用循环4次，并在每个循环中找到最大值（并在每次迭代中将旧的最大值更改为-infinity）将比更“复杂”的方法更有效，因为它需要顺序读取并具有相当小的常量。 对于较大的k ，这当然不是真的，对于k->n ，这衰减为O(n^2)
EDIT2：基准测试：
为了好玩，我在附加代码上运行了一个基准测试。 结果是：
[naive, sort, heap] = [9032, 214902, 7531]
我们可以看到天真和堆比基于排序的方法好得多，并且天真比基于堆的稍微慢一些。 我做了一个wilcoxon测试来检查天真和堆之间的差异是否具有统计显着性，我的P_Value为3.4573e-17 。 这意味着两种方法“相同”的概率是3.4573e-17（非常小）。 由此我们可以得出结论 – 基于堆的解决方案提供了更好的性能，然后是天真的和排序解决方案 （我们凭经validation明了它！）。
附件：我使用的代码：
public static int[] findTopKNaive(int[] arr, int k) { int[] res = new int[k]; for (int j = 0; j < k; j++) { int max=Integer.MIN_VALUE, maxIdx = -1; for (int i = 0; i < arr.length; i++) { if (max < arr[i]) { max = arr[i]; maxIdx = i; } } arr[maxIdx] = Integer.MIN_VALUE; res[k-1-j] = max; } return res; } public static int[] findTopKSort(int[] arr, int k) { Arrays.sort(arr); return Arrays.copyOfRange(arr, arr.length-k,arr.length); } public static int[] findTopKHeap(int[] arr, int k) { PriorityQueue pq = new PriorityQueue (); for (int x : arr) { if (pq.size() < k) pq.add(x); else if (pq.peek() < x) { pq.poll(); pq.add(x); } } int[] res = new int[k]; for (int i =0; i < k; i++) res[i] = pq.poll(); return res; } public static int[] createRandomArray(int n, Random r) { int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = r.nextInt(); return arr; } public static void main(String... args) throws Exception { Random r = new Random(1); int k = 4; int repeats = 200; int n = 5000000; long[][] results = new long[3][repeats]; for (int i = 0; i < repeats; i++) { int[] arr = createRandomArray(n, r); int[] myCopy; myCopy = Arrays.copyOf(arr, n); long start = System.currentTimeMillis(); findTopKNaive(myCopy, k); results[0][i] = System.currentTimeMillis() - start; myCopy = Arrays.copyOf(arr, n); start = System.currentTimeMillis(); findTopKSort(myCopy, k); results[1][i] = System.currentTimeMillis() - start; myCopy = Arrays.copyOf(arr, n); start = System.currentTimeMillis(); findTopKHeap(myCopy, k); results[2][i] = System.currentTimeMillis() - start; } long[] sums = new long[3]; for (int i = 0; i < repeats; i++) for (int j = 0; j < 3; j++) sums[j] += results[j][i]; System.out.println(Arrays.toString(sums)); System.out.println("results for statistic test:"); for (int i = 0; i < repeats; i++) { System.out.println(results[0][i] + " " + results[2][i]); } }
你应该看看Peter Lawrey的这个答案 。 基本上，我们的想法是遍历您的数组，将每个元素添加到SortedSet并通过删除每次迭代中的最小元素将大小保持为4。 该过程为O（n），即使在最坏的情况下，与O（n logn）典型和O（n 2 ）最坏情况相比，对arrays进行完全排序。
final List input = new ArrayList(Arrays.asList(1232, -1221, 0, 345, 78, 99)); final NavigableSet topFour = new TreeSet<>(); for (int i : input) { topFour.add(i); if (topFour.size() > 4) topFour.remove(topFour.first()); } System.out.println(topFour);
最简单的方法是对数组进行排序并获取第一个/最后4个元素。
最后，最多4个条目可以在任何地方，所以无论你做什么，你需要读取整个数组，它将是一个O（n）操作。
关于对arrays进行排序之前的提及确实提供了最简单的方法，但并不是真正最有效的方法。
QuickSort（Quickselect）的变体可用于查找集合中的第k个最大/最小值。
http://en.wikipedia.org/wiki/Selection_algorithm
正确的实现允许您在O（n）时间内获得第k个最大值。
基本上你使用一个枢轴在quicksort中进行分区，并将每次迭代后的轴位置与你想要的位置（在你的情况下为四个）进行比较，如果它相等，则返回位置，否则，将算法应用于输入的正确一半。
当你找到第k个最大值的索引时，你可以简单地遍历数组并获得低于input[k] 。
这可能对你的情况有点过分，因为你只需要四个，但这是最通用的方法。
如果你不太关心内存，你也可以使用一个有界的PriorityQueue来保存顶部/底部的X值，并简单地在Queue中插入所有内容。 剩下的就是你感兴趣的价值观。
排序 ：对数组进行排序并获取最后四个元素
Min Heap：最简单的解决方案是维持最大4的最小堆 。
该解决方案是O（nlogk）复杂度，其中n是元素的数量，k是您需要的元素的数量。
优先级队列 ：您可以创建具有固定大小的PriorityQueue和自定义比较器，如本问题与实现中所述。
选择算法：你可以使用选择算法 ，你可以找到第（nk）个最大元素，然后返回高于这个元素的所有元素，但是它更难实现。 最佳案例复杂性： O（n）
float a[] = {1.0f,3.0f,5.0f,6.0f,7.0f,10.0f,11.0f,3.2f,4.0f}; float first =0.0f; float second=0.0f; float third =0.0f; for (int i=0; i second){ second = a[j]; } } System.out.println("second largest is "+second); for (int k=0;kthird){ third =a[k]; } } System.out.println("third largest is "+third);