14

これは一種の宿題の質問です。私はかなり長い間考えていて、いくつかの解決策を思いつきましたが、より良い解決策が存在すると思います。

配列に 1 回だけ現れる要素 (int) があるかどうかを判断する最も速い方法は何ですか? どの要素も何回でも出現できます。{3, 1, 4, 1, 4, 3} は false を返しますが、{3, 1, 4, 1, 4, 1} は true を返します (3 は 1 回表示されます)。

すでに学んだこと (すべての基本、再帰、oop、クイックソートを含む検索とソートのアルゴリズム) のみを使用することが許可されているため、ハッシュ テーブルを作成することはできません。

これまでのところ、私が思いついた最善の実用的な解決策は、クイックソートを使用して並べ替えてから実行することです（ O(nlogn) ）。ハッシュテーブルに似た場所（ただし、その配列は実際に実装するには大きすぎます）（ O(n) ）

O(n) 時間でこれを行う別の (実用的な) 方法はありますか?

編集: TA から回答を得たところ、私が聞いた提案された O(n) ソリューションは非現実的なもの (私が提案したものと同じまたは類似) であったため、使用しないように言われました。最善の実用的な答え (ハッシュ テーブルを除く) は O(nlogn) 時間であると 99% 確信しています。

4

3 に答える 3

5

後でソートされた配列を反復処理することなく、カスタマイズされたクイックソートを使用して個別の値を見つけることができます。

ピボット値を選択し、配列のそれぞれの部分を移動している場合、値がピボットと一致する場合は、それを破棄し、配列の部分を移動した後にピボット値を破棄すると、配列の前に重複が削除されます最終的にソートされます。

すなわち:

Sorting [5, 1, 4, 1, 4, 1]
If you choose the pivot as 4, you'd end up with the 2 sub arrays being:
[1, 1, 1] and [5]

ピボットが破棄されない場合は区別されます。破棄される場合は、サブリストで同じプロセスを実行します。サブリストに要素が 1 つしかない場合、それは区別されます。

このようにして、個別の値をはるかに早く取得できます。

編集:はい、これはまだ O(nlogn) によって制限されています(私は思いますか?)

于 2013-05-15T16:29:34.100 に答える
0

実験をしましょう:

package test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * User: Nicholas
 * Date: 15.05.13
 * Time: 21:16
 */
public class Searcher {

    private static boolean searchBySorting(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        Arrays.sort(newArray);
        for (int i = 0; i < newArray.length - 2; ++i){
            if(newArray[i] == newArray[i + 1]){
                return true;
            }
        }

        return false;
    }

    private static boolean searchByCompare(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        for (int i = 0; i < newArray.length - 1; ++i){
            int value = newArray[i];
            for(int j = i + 1; j < newArray.length - 1; ++j){
                if(value == newArray[j]){
                    return true;
                }
            }
        }

        return false;
    }

    private static boolean searchBySet(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < newArray.length; ++i){
            if(set.contains(newArray[i])){
                return true;
            }

            set.add(newArray[i]);
        }

        return false;
    }

    private static int [] generateRandomArray(){
        Random random = new Random();
        int size = random.nextInt(1000) + 100;
        int [] array = new int[size];

        for (int i = 0; i < size; ++i){
            array[i] = random.nextInt();
        }

        return array;
    }

    public static void main(String [] args){

        long sortingTime = 0;
        long compareTime = 0;
        long setTime = 0;

        for (int i = 0; i < 1000; ++i){
            int [] array = generateRandomArray();

            long begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchBySorting(array);
            }
            long end = System.currentTimeMillis();
            sortingTime += (end - begin);

            begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchByCompare(array);
            }
            end = System.currentTimeMillis();
            compareTime += (end - begin);

            begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchBySet(array);
            }
            end = System.currentTimeMillis();
            setTime += (end - begin);
        }

        System.out.println("Search by sorting: " + sortingTime + " ms");
        System.out.println("Search by compare: " + compareTime + " ms");
        System.out.println("Search by insert: " + setTime + " ms");
    }
}

私の結果:

ソートによる検索: 2136 ms

比較による検索: 11955 ミリ秒

挿入による検索: 4151 ms

質問はありますか？

PS。私が知っている最高のアルゴリズムは亀とウサギ

于 2013-05-15T17:51:31.110 に答える
0

基本的に、バブルソート スタイルの比較を行う必要があります。この問題に答える組み込み関数はありません。また、並べ替えを行ったとしても、すべての要素を繰り返し処理する必要があります (グループがいつ壊れるかを見つけるだけでも)。特にどの要素が一度だけ返されるかを見つける必要がある場合は、複数の配列を使用してより複雑なアプローチを行うことができます。

しかし、一度現れるものを見つけたら、壊すことができます。このコードはそれを行います。これは O(n^2) ですが、この問題をより速く処理できるかどうかはわかりません。

boolean anySingles(int[] data])
{
 outer:
 for (int i = 0; i < data.length - 1; i++)
 {
  for (int j = 0; i < data.length; j++)
  {
   if (i != j)
   {
    if (data[i] == data[j]) continue outer;
   }
  }
  // made it to the end without finding a duplicate
  return true;
 }
 return false;
}
于 2013-05-15T16:18:59.457 に答える