Блог

Главная - Вопросы по программированию - наибольшее число с каждой цифрой только подкачки не более K раз и только смежной подкачки

наибольшее число с каждой цифрой только подкачки не более K раз и только смежной подкачки

#c #arrays #algorithm

#c #массивы #алгоритм

Вопрос:

У меня был тест, и возникла проблема, которую я до сих пор не могу решить.
Учитывая массив чисел, в котором для КАЖДОГО ЭЛЕМЕНТА разрешено не более K подкачки и только смежная подкачка, найдите наибольший лексикографический порядок.
Пример:

 Input
[7, 1, 2, 3, 4, 5, 6]
swapTime = 2

Output
[7, 3, 4, 1, 2, 6, 5]

Сначала я подумал, что это модифицированная сортировка пузырьков, но это было неправильно, есть идеи?
Вот псевдокод:

 void findMaxNum(int num[], int swapTime) {
    int table[n];
    for(i=0; i<n;   i) 
        table[i] = swapTime;

    for(i=0; i<n-1;   i)
        for(j=0; j<n-i-1;   j)
            if(table[j]!=0 amp;amp; num[j]<num[j 1]) {
                swap(num[j], num[j 1]);
                swap(table[j], table[j 1]);
                table[j]--;
                table[j 1]--;
            }
}

Комментарии:

1. Каковы ограничения на размер массива и обмены?

2. размер массива: 1 <= n <= 10 ^ 5, подкачки: каждый элемент (цифра) имеет свой собственный счетчик подкачки и может меняться только рядом. Пример: 1 2 3 4, вы можете поменять 1 2, но не 1 3 (или 1 4), чтобы поменять 1 3, вам нужно сначала поменять 1 2 (2 1 3 4), затем поменять 1 3 (2 3 1 4) и так далее

3. Так swapTime сколько раз можно перемещать каждый элемент, а не общее количество обменов?

4. Как насчет жадного подхода? Для вашего вывода выполните операцию, которая позволит получить наибольшее число, output[0] сколько сможете, затем выполните операцию, которая позволит получить наибольшее число, output[1] которое вы можете, повторите для всего вывода

Ответ №1:

Вы можете обойтись с максимальной кучей размером k 1, изначально имеющей первые значения k 1 и хэш от каждого индекса до крайнего левого допустимого элемента для этого индекса (без учета индексов <= k).

Затем мы делаем следующее для каждого индекса i в порядке возрастания:

Если hash[i] имеет значение, поместите его в i и удалите из кучи. Если нет, переместите значение max elt из кучи в i и удалите его из хэша. В любом случае добавьте следующий элемент elt из массива в кучу.

Хэш гарантирует, что ни один элемент не перемещается более чем на k вправо. Минимальная куча выбирает максимальный допустимый элемент, гарантируя, что ни один элемент не сдвинется больше, чем на k влево.

Ответ №2:

Для лексикографического порядка вы должны максимально увеличить первую букву, затем 2-ю и так далее. Таким образом, вам не нужно беспокоиться об использовании свопов для цифры, если это помогает улучшить текущую позицию (слева направо) и не превышает k. Вот решение (также модифицирующее ввод, как ваш метод):

 public static void findMax(int[] num, int swapsPerElement) {
    int[] swaps = new int[num.length];
    for (int i = 0; i < num.length; i  ) {
        if (swaps[i] == swapsPerElement)
            continue;
        int best = i;
        for (int j = i   1; j < num.length amp;amp; j - i <= swapsPerElement; j  ) {
            if (swaps[j] == swapsPerElement)
                break; // cannot be swapped
            if (num[best] < num[j] amp;amp; swapsPerElement - swaps[j] >= j - i)
                best = j;
        }
        for (int j = best; j > i; j--) { // swap
            int t = swaps[j]   1;
            swaps[j] = swaps[j - 1]   1;
            swaps[j - 1] = t;
            t = num[j];
            num[j] = num[j - 1];
            num[j - 1] = t;
        }
    }
}