1

整数の 2 つの配列が与えられた場合、2 つの配列に共通の要素があるかどうかを効率的に調べるにはどうすればよいでしょうか?

誰かがこれよりも優れたスペースの複雑さを思いつくことができますか (プログラムのエラーを指摘していただければ幸いです、ありがとう!!)。

XORを使用してこれを解決することは可能ですか?

public boolean findcommon(int[] arr1, int[] arr2) {
  Set<int> s = new Hashset<int>();
  for(int i=0;i<arr1.length;i++) {
    if(!s.contains(arr1[i]))
      s.add(arr1[i]);
  }
  for(int i=0;i<arr2.length;i++) {
    if(s.contains(arr2[i]))
        return true;
  }
  return false;
}
4

4 に答える 4

2

よりスペース効率の高いソリューションを求めているため:

O(n log n) のランタイムを受け入れ、配列の変更が許可されている場合は、配列を並べ替えてから線形パスを実行して、共通の要素を見つけることができます。

于 2013-01-27T09:37:02.397 に答える
1

1回だけ実行する必要がある場合は、時間計算量O（n + m）よりもうまく実行することはできません。ここで、nとmはそれぞれ配列の長さです。両方の配列で入力を実行する必要があります。選択の余地はありません（他にすべての入力をどのように確認しますか？）。したがって、入力処理だけがその複雑さを持ち、より効率的なことを行う意味はありません。配列が大きくなるにつれて検索を続ける必要がある場合、それは別の議論です。

では、提案された実装方法に関する質問は、「含む」にどれくらいの時間がかかるかということです。ハッシュセットを使用しているため、containsは定数時間O（1）であるため、O（n）にアクセスしてハッシュセットを作成し、O（m）にアクセスして2番目の配列の要素を検証します。まとめると、O（n + m）。十分です;）

スペースの複雑さを改善したい場合は、まず、元のアレイに変更を加えることができる必要があります。しかし、O（n）よりも少ない追加スペースを使用し、それでもO（n + m）時間で実行する方法はないと思います。

注：あなたがどのXORを考えているのかわかりません。ビット単位または論理XORを考えている場合、ここでは使用できません。Set XORについて考えている場合は、Javaセットの実装には含まれていないため、論理的に有用かどうかは関係ありません。そのため、独自のセットを作成する必要があります。

于 2013-01-27T09:28:43.770 に答える
1

ソリューションが両方の配列に存在する要素があるかどうかを検出しようとするだけであるとすると、以下はそれを実行するコードです。

 public boolean findCommon(int[] arr1, int[] arr2) {
      HashTable hash = new HashTable();
      for (item : arr1){
         if !(hash.containsKey(item)){
            hash.put(item, "foo");
         }
      }
      for (item : arr2){
         if (hash.containsKey(item)){
           return(true);
         }
      }
      return(false);
 }

これは、単一の要素を共有しない2つの配列の場合でも最悪の場合のO（n）の複雑さを持っています。最初の質問で示唆されているように、心配しているのがスペースの複雑さである場合（たとえば、HashTableを格納する必要がない場合は、パフォーマンスヒットを喜んで受け入れることができます）、これらの線に沿って何かを探すことができます：

    public boolean findCommon(int[] arr1, int[] arr2){
        for (item : arr1){
           for(item2 : arr2){
               if(item ==item2){
                   return(true);
               }
           }
        }
        return(false);
    }

これでスペースの複雑さの問題は解決しますが、（客観的にひどい）時間の複雑さはO（n ^ 2）になります。

これは、より多くのパラメーターを配置する場合に簡略化できます（配列の少なくとも1つがソートされていること、さらには両方がソートされていることを知っているとします）。

しかし、あなたが尋ねたワイルドカードの例では、実際には、スペースの複雑さのHashTableを使用するO（n）、またはスペースの複雑さを軽減するO（n ^ 2）になります。

于 2013-01-27T09:32:40.777 に答える
0

次数 O(n*m) のアルゴリズムを使用して、スペースの占有を改善できます (これが問題ですよね?)。要素のすべてのペアを取得して比較するだけです...これは時間的にはひどいですが、追加のメモリは使用しません。それ以外の場合は、2 つの配列をその場で並べ替え (変更が許可されている場合)、O(max(n,m)) で共通の要素を見つけることができます。

于 2013-01-27T09:38:34.067 に答える