返回具有重复项的子集

Question

我的问题是如何检测另一个子字符串中不存在的数组子集上的重复项？

例如 Input: arr1 = 1,2,3 arr2 = 1,1

Output: Arr2 is not a subset of Arr1

到目前为止，其他一切工作正常，我希望它如何工作，但这个重复的一直返回它是一个子集。我尝试通过将元素放在 for 循环中来删除元素，但作为 else if 但我不认为它是它。删除两个字符串上的相同元素，然后再次循环到

package com.company;

public class RandomArrayFunctionalities
{
    public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo)
    {
        //
        int i, j;

        for(i = 0; i < sizeTwo; i++)
        {
            for(j = 0; j< sizeOne; j++)
            {
                if(Array2[i] == Array1[j])
                {
                    for(i = 0; i < sizeOne - 1; i++)
                    {

                        Array1[i] = Array1[i + 1];

                        /* Decrement array size by 1 */
                        sizeOne--;

                        for(j = 0; j < sizeTwo-1; j++)
                        {
                            sizeTwo--;

                            if(Array2[i] == Array1[j])
                            {

                                break;
                            }
                        }
                        if(j == sizeOne)
                        {
                            return false;
                        }
                        else
                        {
                            return true;
                        }
                    }

                    break;
                }
            }
            if (j == sizeOne)
            {
                return false;
            }
        }
        return true;
    }
}

public static void main(String[] args)
    {
        RandomArrayFunctionalities ranMethod = new RandomArrayFunctionalities();

        int arr1[] = {1, 2, 3};
        int arr2[] = {1,1};

        int sizeOne = arr1.length;;
        int sizeTwo = arr2.length;;

        if(ranMethod.subSet(arr1, arr2, sizeOne, sizeTwo))
        {
            System.out.println("\nArray 2 is a subset of array 1\n");
        }
        else
        {
            System.out.println("\nArray 2 is not a subset of array 1\n");
        }
    }

Answer 1

方案1使用Set记录那些匹配的索引，当arr2中出现重复值时，我们跳过匹配的索引并尝试在arr1中找到花药重复的值。

public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo) {
    if (Array2.length == 0 || Array2.length > Array1.length) {
        return false;
    }
    Set<Integer> matchedIndex = new HashSet<Integer>();
    for (int index = 0; index < Array2.length; index++) {
        boolean matched = false;
        for (int k = 0; k < Array1.length; k++) {
            if (matchedIndex.contains(k)) {
                continue;
            }
            if (Array1[k] == Array2[index]) {
                matched = true;
                matchedIndex.add(k);
                break;
            }
        }
        if (!matched) {
            return false;
        }
    }
    return true;
}

选项 2 对两个数组进行排序，arr1 中的每个值只比较一次

public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo) {
    if (Array2.length == 0 || Array2.length > Array1.length) {
        return false;
    }
    /**
     * make a copy of arrays of the original array should not be modified
     */
    Arrays.sort(Array1);
    Arrays.sort(Array2);
    int k = 0;
    for (int index = 0; index < Array2.length; index++) {
        boolean matched = false;
        for (; k < Array1.length; k++) {
            if (Array1[k] == Array2[index]) {
                k++;
                matched = true;
                break;
            }
        }
        if (!matched) {
            return false;
        }
    }
    return true;
}

Answer 2

我会采用完全不同的方法。我会使用 List class 并使用以下逻辑来检查一个数组是否是另一个数组的子集：

public boolean isSubset(int[] arr1, int[] arr2)
{
    // turn the first array into a list to make removing items easier.
    List<Integer> list1 = Arrays.stream(arr1).boxed().collect(Collectors.toList());

    for (Integer currentElement : arr2)
    {
        if (!list1.contains(currentElement)) // Check if list1 contains the element of list2, if not return false
        {
            return false;
        }

        list1.remove(currentElement); // we checked that the list has the currentElement, but if list2 has the element twice, then list1 must have it twice too, so we remove it to make sure that each element has the same count in list1 as in list2
    }

    return true;
}

这样你就不需要对任何东西进行排序，只需很少的几行就可以解决。 list1.remove() 可以检查元素的数量是否相同。

Answer 3

我认为您在实现中遇到的问题之一是当元素位于子列表中时不删除主列表中的元素。
所以当你检查第二个“1”时，它仍然存在于主列表中。

我会按如下方式进行。应该有更多的检查子列表是否比主列表大但是很容易添加。

public static void main(final String[] args) {
    final List<String> main = Arrays.asList("1", "2", "3");
    final List<String> subset = Arrays.asList("1", "2");
    final List<String> notSubset = Arrays.asList("1", "1");

    displaySubsetOrNot(main, subset);
    displaySubsetOrNot(main, notSubset);
}

private static void displaySubsetOrNot(final List<String> main, final List<String> subset) {
    if (isSubset(main, subset)) {
        System.out.println("subset");
    } else {
        System.out.println("not subset");
    }
}

private static boolean isSubset(final List<String> mainList, final List<String> subsetList) {
    final List<String> mainListCopy = new ArrayList<>(mainList);
    for (final String element : subsetList) {
        if (!mainListCopy.remove(element)) {
            return false;
        }
    }
    return true;
}

Answer 4

应为两个阵列创建频率图，并且需要计算频率差异：

for each key in map2:
    map2.put(map2.get(key) - map1.getOrDefault(key, 0))

如果 map2 包含所有小于或等于 0 的频率，则 arr2 是 arr1 的“子集”。

public static boolean subSet(int[] arr1, int[] arr2) {
    Map<Integer, Integer> freq1 = Arrays.stream(arr1).boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));
    Map<Integer, Integer> freq2 = Arrays.stream(arr2).boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));
    
    freq2.forEach((k, v) -> freq2.put(k, v - freq1.getOrDefault(k, 0)));

    // debug print
    System.out.println("freq2: " + freq2);

    return freq2.values().stream().allMatch(x -> 0 >= x);
}

测试：

System.out.println(subSet(new int[]{1, 2, 3}, new int[]{1, 1}));
System.out.println(subSet(new int[]{1, 2, 3}, new int[]{1, 3}));
System.out.println(subSet(new int[]{1, 2, 3, 1}, new int[]{1, 1}));

输出：

freq2: {1=1}
false
freq2: {1=0, 3=0}
true
freq2: {1=0}
true

或者只为 arr1 创建一张地图，然后 arr2 的元素可以从 map1 的频率中“减去”，一旦出现负值， false 返回：

public static boolean subSet(int[] arr1, int[] arr2) {
    Map<Integer, Integer> freq1 = Arrays.stream(arr1)
        .boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));

    for (int x : arr2) {
        if (freq1.merge(x, -1, Integer::sum) < 0) {
            return false;
        }
    }
    return true;
}

返回具有重复项的子集

Returning a subset that has a duplicate

java

arraylist