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

rkttyhzu  于 2021-07-08  发布在  Java
关注(0)|答案(1)|浏览(354)

我试图解决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);
        }

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

vktxenjb

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);
    }

}

相关问题