Блог

Я пытался решить проблему ХакеррАнка на 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);
        }

 

Пожалуйста, скажите мне, где мой код пошел не так.

В чем смысл этой строки?

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

Я не вижу в вашем коде ничего медленного. Мне просто интересно, как вы можете отслеживать уникальные числа, используя set, учитывая, что set сообщает вам только о том, существует ли такое число (но не о том, сколько вхождений одного и того же числа существует). И вы не хотите продолжать сканирование deque, чтобы увидеть, является ли удаляемое число последним.

Я не думаю, что это отличный / быстрый код, но, похоже, он проходит тесты. Я подсчитываю, сколько из каждого целого числа находится в окне, используя карту (и использую часть вашего кода).

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

}

 

Просто хотел поделиться тем, как я решил это, если это поможет.

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

Мы можем немного оптимизировать пространство, избегая хэш-карты все вместе, но, похоже, 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() amp;amp; 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() amp;amp; nums[deque.peekLast()] == nums[i]) {
                deque.removeLast();
            }

            deque.addLast(i);

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

        return maxUniqueCount;
    }