3

整数配列のすべての要素がJavaの別の配列のすべての要素のサブセットであるかどうかを効率的に確認するにはどうすればよいですか？たとえば、[331123]は[11233342]のサブセットです。前もって感謝します。

4

7 に答える 7

9

配列の使用に縛られていない場合、Javaコレクションには次のcontainsAllメソッドがあります。

boolean isSubset = bigList.containsAll(smallList);

これにより、必要なことを効率的に実行できます。

于 2013-03-26T03:12:13.280 に答える
3

AがBのサブセットであることを確認したいとします。Bの各要素をハッシュに入れてから、Aの要素を反復処理します。これらはすべて、ハッシュに存在する必要があります。

于 2013-03-26T03:06:29.933 に答える
3

スーパーHashSetセット配列から作成します。サブセット配列の各要素がに含まれているかどうかを確認しHashSetます。これは非常に高速な操作です。

于 2013-03-26T03:08:47.753 に答える
1

外側のループは、arr2[]のすべての要素を1つずつ選択します。内側のループは、外側のループによって選択された要素を線形に検索します。すべての要素が見つかった場合はtrueを返し、見つからなかった場合はfalseを返します。

boolean checkIsSubset（int arr1 []、int arr2 []）{

    int m=arr1.length,  n=arr2.length;
    int i = 0;
    int j = 0;
    for (i=0; i<n; i++){
        for (j = 0; j<m; j++){
           if(arr2[i] == arr1[j])
              break;
        }
        if (j == m)
           return false;
    }
    return true;
}

ソート後にバイナリ検索を行うのはなぜですか？両方の配列がソートされた形式で利用できるため、次のように2つのポインターを使用できます。

boolean isSubset（int arr1 []、int arr2 []、int m、int n）{

int i = 0, j = 0;
quickSort(arr1, 0, m-1);
quickSort(arr2, 0, n-1);
while( i < n && j < m )
{
    if( arr1[j] <arr2[i] )
        j++;
    else if( arr1[j] == arr2[i] )
    {
        j++;
        i++;
    }
    else if( arr1[j] > arr2[i] )
        return false;
}

if( i < n )
    return false;
else
    return true;

}

于 2016-07-22T07:06:37.733 に答える
1

私は2つの異なる解決策を持ってきました

入力： int mainArray[] = { 1, 2, 3, 2, 5, 6, 2 }, subArray[] = { 2, 2, 2 };

  • 最初のソリューションは、両方の配列を繰り返して比較し、 main[i] = -1要素が再び含まれるのを避けるために使用されます

    void findIfArrayIsASubset(int[] main, int[] sub) {
int count = 0;
for (int i = 0; i < main.length; i++) {
    for (int j = 0; j < sub.length; j++) {
        if (main[i] == sub[j]) {
            main[i] = -1;
            count++;
            break;
        }
    }
}
if (count == sub.length)
    System.out.println("is a subset");
else
    System.out.println("is not a subset");
}

  • 1....92番目のソリューションは、からのキーと値をとして持つハッシュマップを使用します。 次に、メイン配列を反復処理し0、次にそれぞれの値を 反復処理し、次にサブ配列を反復処理し 、ハッシュマップの値の合計を2つの配列の長さの差に変換します。
    +1
    -1

    void findIfArrayIsASubset(int[] main, int[] sub) {
Map<Integer, Integer> mainMap = new HashMap<Integer, Integer>();
for (int i = 0; i < 10; i++) {
    mainMap.put(i, 0);
}
for (int i = 0; i < main.length; i++) {
    mainMap.put(main[i], mainMap.get(main[i]) + 1);
}
for (int i = 0; i < sub.length; i++) {
    mainMap.put(main[i], mainMap.get(main[i]) - 1);
}
String output = mainMap.values().stream().reduce(0, Integer::sum).compareTo(main.length - sub.length) == 0
        ? "is a subset" : "not a subset";
System.out.println(output);
}
于 2016-12-05T12:13:08.657 に答える
0

両方の配列を並べ替えて、小さい配列のすべての要素が大きい配列に存在することを確認します。これは余分なスペースを使用せずにあります。

誰かがすでに提案したようにhasmapを使用しない場合。

于 2018-12-27T21:52:51.943 に答える
-1

これにより、可能なサブセットの要素が大きい配列から欠落していないかどうかがチェックされます。もしそうなら、それはサブセットではありません：

boolean isSubset(int[] a1, int[] a2) {
    a2 = Arrays.copyOf(a2, a2.length);
    Arrays.sort(a2);
    for(int e : a1) {
        if (Arrays.binarySearch(a2, e) < 0) {
            return false;
        }
    }
    return true;
}
于 2013-03-26T03:13:41.837 に答える