Переупорядочение массива s.t. нет дубликатов в группе

Question

Так что я пытаюсь работать через следующий вопрос интервью:

/** Given an unordered array of positive integers, create an algorithm that makes sure 
no group of integers of size bigger than M have the same integers. 

Input: 2,1,1,1,3,4,4,4,5 M = 2 
Output: 2,1,1,3,1,4,4,5,4 
*/ 

Я думал о О (п^2) решения: перебирает массив и своп примыкающего которые повторяются в данной группе. Но поскольку у вас есть случай, например, 1,2,3,4,1,1 M = 2, вам придется обернуть вокруг задней части массива потенциально n раз, предоставив вам время полинома.

Так что я хотя следующее решение, которое, как предполагается работать в линейном времени:

public static int[] regroup(int[] input, int m) { 
    HashMap<Integer, Integer> map = new HashMap<>(); 
    for (int i : input) { 
     if (!map.containsKey(i)) { 
      map.put(i, 1); 
     } else { 
      map.put(i, map.get(i) + 1); 
     } 
    } 
    int i = 0, n = 0; 
    while (i < input.length) { 
     for (int curr : map.keySet()) { 
      if (n == m) { 
       n = 0; 
       break; 
      } 
      if (map.get(curr) > 0) { 
       input[i] = curr; 
       map.put(curr, map.get(curr) - 1); 
       i++; n++; 
      } else { 
       continue; 
      } 
     }  
    } 
    return input; 
} 

Это по существу делает HashMap со всеми значениями в их # появлений, затем выбирает один элемент из каждого ведро для каждой группы размера М, гарантируя уникальные предметы. Хотя проблема я столкнулся, заключается в следующем контрпример:

{2,1,1,1,3,4,4,4,5} M = 3 

Это возвращает

[1, 2, 3, 1, 4, 5, 1, 4, 4] 

Который явно не прав. Случилось то, что в конце концов у него были уникальные предметы, поэтому нужно просто поместить 4 раза в эту последнюю группу. Может ли кто-нибудь подумать о том, как решить эти проблемы и сохранить линейное время?

Answer 1

Как только вы подсчитали весь элемент, поместите их в кучу (число, счет). возьмите пару из кучи и начните распространять их во входном массиве с разницей M, пока не достигнете конца входного массива. Как только вы достигнете конца массива, начните со следующей позиции с предыдущего начала массива. приведенный ниже:

 int curr = 0; 
    int start = curr; 
    while(maxHeap.size() > 0){ 
      Pair p = maxHeap.poll(); 
      int i =0; 
      while(i < p.count){ 
       input[start] = p.num; 
// keep putting element at gap of m 
       start = start + m; 
// if exceeded the length of input array , wrap around with previous start +1. 
       if(start >= input.length){ 
        curr++; 
        start = current; 
       } 
       i++; 
      } 
     } 
     return true; 
    }