javadeque(从子数组中查找唯一整数的最大数目)

rkttyhzu 于 2021-07-08 发布在 Java

关注(0)|答案(1)|浏览(365)

我试图解决javadeque上的hackerrank问题。我的代码通过了所有的案例，除了那些有100000个输入的案例。
问题：在这个问题中，给你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);
        }

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

Java HashSet sub-array Deque

来源：https://stackoverflow.com/questions/64983328/java-deque-finding-the-max-number-of-unique-integers-from-subarrays

1条答案

按热度按时间

vktxenjb1#

这条线有什么意义？

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

我在你的代码里没有看到任何慢的东西。我只是想知道，如果一个集合只告诉你是否有这样一个数字（而不是同一个数字出现了多少次），那么如何使用集合来跟踪唯一的数字。而且你不想一直扫描数据，看看被删除的号码是不是最后一个。
我认为这不是很好/很快的代码，但它似乎通过了测试用例。我通过使用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);
    }

}

赞(0）回复(0）举报 2021-07-09

我来回答

javadeque(从子数组中查找唯一整数的最大数目)

1条答案

相关问题

热门标签

最新问答