2

搜索属于大型无序整数数组的整数元素的索引和值的最佳方法是什么？哪个是此过程的最佳搜索技术/算法？

int[] temp = new int[]{1,4,3,6,7,8,5,2,9,......}

现在说，我想搜索元素“9”，我还需要获取该元素的索引。我的意思是，对数组元素进行排序并确定它在这里不起作用（因为我还需要跟踪元素的索引）。有什么建议么？顺便说一句，我正在研究java..

4

6 回答 6

6

如果您手动执行此操作，则可以迭代每个数组项：

public int indexOf(int search, int[] arr) {

    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == search) {
            return i;
        }
    }

    return -1;

}

如果你知道数组在多次搜索之间不会改变，你也可以使用 Map 缓存结果。只要你改变数组就清空缓存。

private Map<Integer, Integer> indexCache;

public int indexOf(int search, int[] arr) {

    Integer cachedIndex = indexCache.get(search);
    if(cachedIndex != null) return cachedIndex;

    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == search) {
            indexCache.put(search, i);
            return i;
        }
    }

    return -1;

}

实际上，您最好使用 Map 而不是完全使用数组来存储这些数据，因为它更适合键值查找。

于 2013-03-13T15:57:31.200 回答
2

如果您需要多次搜索（同一个数组），您可能会创建一个临时结构，它结合了原始索引和值：

class Pair implements Comparable<Pair> {
    final int index;
    final int value;

    Pair(int index, int value) {
        this.index = index;
        this.value = value;
    }

    public int compareTo(Pair oth) {
        if (value < oth.value) return -1;
        else if (value > oth.value) return 1;
        else if (index < oth.index) return -1;
        else if (index > oth.index) return 1;
        else return 0;
    }
}

final ArrayList<Pair> list = new ArrayList<Pair>();

for (int k = 0; k < array.length; ++k) {
    list.add(new Pair(k, array[k]);
}

Arrays.sort(list);

现在，list按值排序，然后按索引排序。我们现在可以使用二分搜索（例如）来查找元素。但是请注意，这仅是值得的，如果您搜索值的次数（现在O(log n)与 相对O(n)）支配了构建数组所需的时间（(O(n log n)由于排序）。

HashMap或者，您可以使用or构建一个类似索引的结构TreeMap，它将整数值映射到它在数组中的位置。在使用 的情况下HashMap，访问时间将在 左右O(1)，在使用的情况下，访问时间TreeMap将在 左右，O(log n)就像上面提出的二进制搜索方法一样。

如果您必须经常搜索数组，所有这些建议显然是值得的。

此外，您应该考虑，如果数组相当小，则使用简单的线性搜索（如其他人所建议的那样）实际上可能是最快的解决方案，因为所涉及的“常数”较低且数组组件的局部性很好。

因此，另一种方法可能是Pair在排序为两个整数数组（一个包含值，另一个包含索引）后再次解包结构：

int[] values = new int[list.size()];
int[] indices = new int[list.size()];
int pt = 0;

for (Pair p: list) {
    values[pt] = p.value;
    indices[pt] = p.index;
    pt += 1;
}

现在您可以values使用二进制搜索来搜索数组：

int position = Arrays.binarySearch(values, valueToLookFor);
if (position >= 0) {

    // Found it!
    int index = indices[position];

    System.out.println("Value was originally stored in " + index);

} else {

    // Value not found
}

请记住：最简单的解决方案（线性扫描）可能是最快的，具体取决于数组的大小和您需要搜索条目的次数。我实际上会先尝试一下，并且只使用一个更复杂的建议，如果它被证明是一个瓶颈。

于 2013-03-13T16:17:47.063 回答
1

增强：

  int[] temp = new int[]{1,4,3,6,7,8,5,2,9,......}
    for (int i : temp) {
      if (i == 9)
        // do something
    }
于 2013-03-13T16:00:43.530 回答
0

从头开始，一直持续到结束：然后停止。

刘易斯卡罗尔

当然，除非你在到达终点之前找到你要找的东西。

于 2013-03-13T15:57:04.147 回答
-1

最少的编码是：

Arrays.asList(temp).indexOf(9)
于 2013-03-13T15:56:34.373 回答
-1

更好的方法是先对数组进行排序。

Arrays.sort(array);
Arrays.binarySearch(array, value);

扫描未排序的数组需要线性时间“O(n)”。如果您不想对数组进行排序，可以试试这个：

public int find(int[] array, int value) {
        int index = -1;
        for (int i=0; i<array.length; i++) {
            if(array[i] == value) { index = i; }
        }
        return index;            
    }
于 2013-03-13T15:59:58.577 回答