Java双端队列（查找子数组中独特整数的最大数量）

Question

我试着解决 HackerRank 上一个关于 Java Deque 的问题。我的代码通过了除了含有 100,000 个输入的测试用例以外的所有测试用例。

问题：给定 N 个整数，需要找出大小为 M 的所有可能连续子数组中唯一整数的最大数量。 ---> 我们被给定了 N 个整数，需要在每个大小为 M 的连续子数组中找到"唯一的整数"的数量。然后输出这些"唯一整数"的最大数量。

link: https://www.hackerrank.com/challenges/java-dequeue/problem

我的代码：

public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Deque deque = new ArrayDeque<>();
            HashSet<Integer> set = new HashSet<>();
            int n = in.nextInt();
            int m = in.nextInt();
            int max=0;
            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                deque.add(num);
                set.add(num);
                if(i>=m-1){
                    if(set.size()>max)max=set.size();
                    Integer removed=(Integer)deque.removeFirst();
                    set.remove(removed);
                   set.add((Integer)deque.peek());
                }
                
            }
            System.out.println(max);
        }

请告诉我我的代码哪里出错了。

- Code Hard

Answer 1

这行代码的作用是什么？

                   set.add((Integer)deque.peek());

我没有看到你的代码有什么慢的地方。我只是想知道你是如何使用 set 来跟踪唯一数字的，因为 set 只会告诉你是否有这样的数字存在（但不会告诉你相同数字出现的次数）。而且你不想扫描 deque 来查看被移除的数字是不是最后一个。

我认为这不是很好/快的代码，但它似乎通过了测试用例。我通过使用 map 来记录窗口中每个整数的数量（并使用你的一些代码）来保持计数。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer, Integer> counts = new HashMap<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            int count = counts.getOrDefault(num, 0);
            counts.put(num, ++count);
            if (i >= m - 1) {
                if (counts.size() > max) max = counts.size();
                Integer removed = deque.removeFirst();
                int removing = counts.get(removed);
                removing--;
                if (removing == 0) {
                    counts.remove(removed);
                } else {
                    counts.put(removed, removing);
                }
            }
        }
        System.out.println(max);
    }

}

- Vlad L

---

谢谢您的建议！我使用的逻辑是创建一个大小为M的Deque，在每次迭代中删除第一个元素（同时在末尾添加新元素）。并将元素添加到Set中，以便仅存储唯一数字。 - Code Hard

Answer 2

我想分享一下我是如何解决这个问题的，希望对您有所帮助。

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    Deque deque = new ArrayDeque();
    Set<Integer> integers = new HashSet<>();
    int n = in.nextInt();
    int m = in.nextInt();
    long result = 0;
    for (int i = 0; i < n; i++) {
        int num = in.nextInt();
        deque.add(num);
        integers.add(num);
        if (deque.size() == m) {
            long currentSize = integers.size();
            if (currentSize > result) {
                result = currentSize;
            }
            Integer removed = (Integer) deque.pollFirst();
            if (!deque.contains(removed)) {
                integers.remove(removed);
            }
        }
    }
    System.out.println(result);
}

- aexposito

Answer 3

import java.util.*;
public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int maxUnique = 0;
        Map<Integer, Boolean> uniqSet = new HashMap<>();
        for (int i = 0; i < n; i++) {
          int num = in.nextInt();
           deque.addLast(num);
           uniqSet.put(num, true);
           if(deque.size() == m){
            //  int uniqueSize = new HashSet<>(deque).size();
            int uniqueSize = uniqSet.size();
             maxUnique = Math.max(maxUnique, uniqueSize);
  
             int x = deque.removeFirst();
             if(!deque.contains(x)){
               uniqSet.remove(x);
             }
           }
        }
        in.close();
        System.out.println(maxUnique);
    }
}

- Suresh Nayak

Answer 4

我们可以通过完全避免使用哈希表来稍微优化空间，但似乎Hackerrank并不关心这一点。无论如何，我在这里提供了我的解决方案，它可以使用一个映射来解决这个问题。

private int countUniqueNumsInSubarrays(int[] nums, int m) {
        Deque<Integer> deque = new LinkedList<>();

        int maxUniqueCount = 0;

        for (int i = 0; i < nums.length; i++) {
            // if deque's left entry is outside the window then pop it out
            while (!deque.isEmpty() && i - deque.peekFirst() >= m) {
                deque.removeFirst();
            }

            // this will make sure that the deque only contains unique numbers,
            // this is essentially helps us avoid that extra hash map  
            while (!deque.isEmpty() && nums[deque.peekLast()] == nums[i]) {
                deque.removeLast();
            }

            deque.addLast(i);

            if (i >= m - 1) {
                maxUniqueCount = Math.max(maxUniqueCount, deque.size());
            }
        }

        return maxUniqueCount;
    }

- Ezio

Answer 5

import java.io.*;

导入 java.util.*; 导入 java.util.stream.Stream;

public class Solution {

public static void main(String[] args) {
    var sc = new Scanner(System.in);
    
    var split = sc.nextLine().split(" ");
    int n = Integer.parseInt(split[0]);
    int m = Integer.parseInt(split[1]);
    
    if (!(1 <= n && n <= 100_000)) {
        System.exit(0);
    }
    if (!(1 <= m && m <= 100_000)) {
        System.exit(0);
    }
    if (!(m <= n)) {
        System.exit(0);
    }
    
    split = sc.nextLine().split(" ");
    
    sc.close();
    int maxNumUniqueInt = 0;
    HashSet<Integer> dist = new HashSet<>();
    Deque<Integer> deque = new ArrayDeque<>();
    int[] arr = Stream.of(split).mapToInt(Integer::parseInt).toArray();
    
    for (int i = 0; i < m; i++) {
        deque.addLast(arr[i]);
        dist.add(arr[i]);
    }
    int num = dist.size();
    if (maxNumUniqueInt < num) {
        maxNumUniqueInt = num;
    }
    for (int i = m; i < n; i++) {
        deque.addLast(arr[i]);
        dist.add(arr[i]);
        int remove = deque.removeFirst();
        if (!deque.contains(remove)) {
            dist.remove(remove);
        }
        num = dist.size();
        if (maxNumUniqueInt < num) {
            maxNumUniqueInt = num;
        }
       // System.out.println(i + "  |  " + deque + "  |  " + dist + "  |  " + maxNumUniqueInt);
    }
    
    System.out.println(maxNumUniqueInt);
}

}

- Rafaelbf84

Answer 6

不是试图从hashSet中删除元素，而是只从deque中删除不再在窗口中的元素。如果一个元素不在deque中，意味着它不再在窗口内，所以我们从hashSet中将其删除。

我们检查hashSet.size()是否大于max，以更新唯一元素的最大计数。

public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque deque = new ArrayDeque<Integer>();
        HashSet hashSet = new HashSet<Integer>();
        int n = in.nextInt();
        int m = in.nextInt();
        int max = 1; 
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            hashSet.add(num);
            if (i >= m-1) {
                if (hashSet.size() > max) max = hashSet.size();
                int removeElement = (Integer)deque.remove();
                if (!deque.contains(removeElement)) {
                    hashSet.remove(removeElement);
                }
            }
        }
        System.out.println(max);
    }
}

- Vijay Kumar