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;

}

多くの検索を実行する間に配列が変更されないことがわかっている場合は、マップを使用して結果をキャッシュすることもできます。配列を変更するたびにキャッシュを空にするだけです。

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または、またはを使用してインデックスのような構造を構築することもできますTreeMap。これは、整数値から配列内のその位置にマップされます。を使用する場合HashMap、アクセス時間は、上記で提案された二分探索アプローチO(1)の場合と同様に、約にTreeMapなります。O(log n)

これらの提案はすべて、配列を頻繁に検索する必要がある場合にのみ、明らかに価値があります。

また、配列が適度に小さい場合は、（他の人が提案しているように）単純な線形検索を使用することが、関連する「定数」が低く、配列コンポーネントの局所性が高いため、実際には最速の解決策になる可能性があることを考慮する必要があります。

したがって、さらに別のアプローチは、Pair2つの整数配列（1つは値を含み、もう1つはインデックスを含む）にソートした後、構造を再度解凍することです。

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
}

覚えておいてください：配列のサイズとエントリを検索する必要がある回数によっては、最も単純なソリューション（線形スキャン）が最も速い場合があります。私は実際にそれを最初に試し、それがボトルネックであることが判明した場合は、より複雑な提案の1つのみを使用します。

于 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 に答える