0

我的算法在所有可能的连续子数组中查找唯一整数的最大数量不适用于大量整数和子数组。例如，我必须从控制台读取总共6 个整数，每个子数组的大小为3。所以，对于这种输入 5 3 5 2 3 2 我的程序应该打印3并且这工作正常。第一个子数组存储 5 3 5 所以唯一整数的数量是2。第二个子数组存储 3 5 2 所以唯一整数的数量是3。第三个子数组也会打印3因为它存储 5 2 3 等等......

但是，我的算法似乎无法处理子数组大小为99877的100000个整数。谁能解释我，我做错了什么？ 仅供参考：我必须使用像 LinkedList 或 ArrayDeque 这样的 Deque 实现

for (int i = 0; i < totalAmountOfIntegers; i++) {

    int anyIntegerNumber = consoleInput.nextInt();
    arrayDequeToStoreAllIntegers.addLast(anyIntegerNumber);
    hashSetToStoreUniqueIntegers.add(anyIntegerNumber);

    if (arrayDequeToStoreAllIntegers.size() == sizeOfEachArrayDequeAsSubArray) {

        if (hashSetToStoreUniqueIntegers.size() > quantityOfUniqueIntegersInSubarray) {
            quantityOfUniqueIntegersInSubarray = hashSetToStoreUniqueIntegers.size();
        }

        int firstNumberInDeque = arrayDequeToStoreAllIntegers.remove();
        if (hashSetToStoreUniqueIntegers.size() == sizeOfEachArrayDequeAsSubArray) {
            hashSetToStoreUniqueIntegers.remove(firstNumberInDeque);
        }


    }
}
4

3 回答 3

0

答案就是整个数组中唯一的整数，因为数组是所有子数组的超集，所有数字都将出现在其中
只需找出存在多少唯一元素

于 2017-09-02T13:48:56.340 回答
0

老实说，我不明白你的算法。我并没有真正了解变量所指的内容（尽管它们似乎以语义方式命名）。
但是这个呢： 

import java.util.HashSet;
import java.util.Set;

public class UniqueIntegers {

    public static void main(String[] args) {
        UniqueIntegers ui = new UniqueIntegers();

        Integer[][] integers = {
                {3,5,3,4,6},
                {1,6,3,2,4},
                {2,3,4},
                {3,3,6,9,2}
        };

        Set<Integer> unique = ui.uniqueIntegers(integers);

        System.out.println("Unique Integers: " + unique.size());
        System.out.println("Integers: " + unique);
    }


    private Set<Integer> uniqueIntegers(Integer[][] ints){
        Set<Integer> result = new HashSet<Integer>();

        for (Integer[] iSub : ints){
            for (Integer i : iSub){
                result.add(i);
            }
        }

        return result;
    }

}

它打印：

Unique Integers: 7
Integers: [1, 2, 3, 4, 5, 6, 9]
于 2017-09-02T13:59:25.800 回答
0

经过一天的研究，我发现了我的错误。我的第三个 IF 语句是错误的。我正在比较，如果我的 HashSet 变量的大小等于每个子数组可以容纳的元素的最大大小。
相反，我应该比较我的int变量firstNumberInDeque（我首先从 ArrayDeque 变量中删除）是否包含另一个具有相同值的int变量。因此，如果这是真的，我的 HashSet 变量将保持不变。
但是，如果我的 ArrayDeque 变量不包含另一个与firstNumberInDeque值相同的int ，则应该从我的 HashSet 变量中删除firstNumberInDeque 。这是正确的代码：

int firstNumberInDeque = arrayDequeToStoreAllIntegers.remove();
if (!arrayDequeToStoreAllIntegers.contains(firstNumberInDeque)) {
    hashSetToStoreUniqueIntegers.remove(firstNumberInDeque);
}
于 2017-09-03T15:35:25.233 回答