获取数组中元素索引的快速方法是什么？

Question

我在接受采访时被问到这个问题.虽然采访是针对网点位置的,但他在java的背景下问我这个问题,因为我在简历中也提到了java.

如何在数组中找到值为X的元素的索引？

我说从第一个元素到最后一个元素迭代,并检查值是否为X将给出结果.他询问了一种涉及较少次迭代的方法,我说使用二进制搜索,但这只能用于排序数组.我试着在Array类中使用IndexOf函数.但我身边没有回答这个问题.

有没有快速的方法来获取数组中具有值X的元素的索引？

Answer 1

只要没有关于数组的知识(它是排序的,升序还是降序等等),就没有办法在不检查每个元素的情况下找到元素.

而且,这正是indexOf(当使用列表时).

Answer 2

如何在数组中找到值为X的元素的索引？

这会很快:

int getXIndex(int x){
    myArray[0] = x;
    return 0;
}

您的函数应该接收数组作为参数.除此之外,优秀的答案(这也说明了TDD的一个危险):) (2认同)
我必须开始编写这样的代码 - 它节省了很多时间. (2认同)
@fortran,你__知道upvote按钮的悬停 - 帮助说"有用"而不是"有趣",是吗？我只是为了幽默而且,除非它附带一个_actual_有用的答案,它可能最好留在评论中:-) (2认同)

Answer 3

找到它的一种实用方法是并行处理.

只需将数组划分为N个部分,并将每个部分分配给一个线程,该线程遍历其部分的元素,直到找到值.N应该最好是处理器的核心数.

java为此提供了ParallelArray(generic)和ParallelLongArray(primitive).http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/ParallelLongArray.html.`indexOf`操作使用N分区方案实现. (2认同)