获取数组中n个最小元素的索引
我有一个int数组int[] myArray = new int[100];
并希望获得最小10(任意n)元素的索引。 我怎样才能做到这一点?
创建一个包含数字和索引的对象,然后创建这些对象的数组,然后执行Array.Sort(arrayset [],comparator) java docs 。 然后你可以从排序的数组中挑选出前x个项目。
编辑:这样的事情…… [我用这个按照’距离’排序
import java.util.Arrays; import java.util.Comparator; public class NearestObject { public NearestObject(int position, int distance) { this.Position = position; this.Distance = distance; } public int Position = 0; public int Distance = 0; public static NearestObject[] SortDistance(NearestObject[] items) { Arrays.sort(items, new DistanceSort()); return items; } } class DistanceSort implements Comparator { public int compare(NearestObject o1, NearestObject o2) { return o1.Distance - o2.Distance; } }
对数组进行排序然后选择10很简单,但它是O(n log n),如果你不想重新排序初始数组,你也需要复制它。
更好的想法是使用max-heap(或优先级队列),它在插入元素时自动对元素进行排序,这样最大的元素就是根节点。 沿着arrays走,继续放入元素,直到你达到10; 然后,对于每个后续元素,只需检查它是否小于堆中的最大元素(常量时间检查),如果是,则弹出那个并插入新元素。 当你通过整个数组时,剩下的10件事是你的最小元素。 这样就可以得到O(n log 10)== O(n)的结果,因为每次插入堆只需要花费O(log 10)。
默认情况下,Java的Priority Queue实现是一个最小队列,因此您需要传入一个反转顺序的Comparator。 有关如何执行此操作的示例,请参阅此问题 。 如果要在最后获取索引,则还需要创建包含(值,索引)对的自定义对象。
直接的解决方案是迭代数组并维护您找到的n个最小元素及其索引的列表。 这是O(N)解决方案,在大多数情况下是可接受的。 我猜这是家庭作业,你必须有比O(N)更好的东西。
按索引对它们进行排序并返回前10个
首先创建包含索引和值的结构:
class IndexValue { final int i; final int v; }
然后使用这个新结构创建一个数组:
IndexValue[] array = new IndexValue[myArray.length]; for( int i = 0 ; i < array.length ; i++ ) { array[i] = new IndexValue( i, myArray[i] ); }
最后排序并采用前N个元素
Arrays.sort( array ); // you'll need to implement Comparator though for( int i = 0 ; i< 10 ;i++ ) { System.out.print( array[i] ); }
这是完整的工作代码:
import java.util.Arrays; import java.util.Random; import java.util.Comparator; import static java.lang.System.out; class IndexValue { final int i,v; public IndexValue( int i, int v ) { this.i = i; this.v = v; } } public class SortByIndex { public static void main( String [] args ) { Random random = new Random(); int [] myArray = new int[100]; IndexValue[] array = new IndexValue[myArray.length]; // Fill the array for( int i = 0 ; i < 100; i++ ) { myArray[i] = random.nextInt(); array[i] = new IndexValue( i, myArray[i] ); } // Sort it Arrays.sort( array, new Comparator(){ public int compare( IndexValue a, IndexValue b ){ return av - bv; } }); // Print it out.println("Top:"); for( int i = 0 ; i < 10 ; i++ ) { out.println( String.format("array[%d]=%d", array[i].i, array[i].v )); } } }
您可以对数组进行排序,循环前10个元素,然后为每个元素搜索到数组中它所具有的位置…也许它不是更有效的方式,但它更容易。
如果您正在寻找一个实际的答案(与实际的排序算法等),那么只需使用HashMap或PriorityQueue。 如果速度不是问题,请试试这个简单的算法。 它比PriorityQueue更容易,因为您不需要自定义对象:
HashMap
填充indexMap,这样我们就可以获得数组中任何给定数字的索引
for (int index = 0; index <= array.size; index++) { if (indexMap.get(array[index]) == null) { // Prime it with an ArrayList indexMap.put(array[index], new ArrayList()); } indexMap.get(array[index]).add(index); }
对于数组中最小的n个数字,打印出它们的索引。
Arrays.sort(array); for (int index = 0; index <= n; index++) { System.out.println(indexMap.get(array[index]).remove(0)); }
- 转换时Gson忽略了我的字段
- Roboelectric给了我一个java.lang.IllegalArgumentException:需要INTERNET权限
- Java – ByteArrayOutputStream是否安全,没有flush()和close()?
- 如何将所有ArrayList <ArrayList >值存储到ArrayList 中?
- 我在哪里可以看到日志,如果我在电话上安装了应用程序?
- TextView Android里面的可点击单词
- 将JSON解析为自定义ArrayList,仅返回最后一项?
- Android – 应用程序关闭时从另一个类调用方法(使用AlarmManager)
- 如何标记java代码,使其不被编译