largest number with each digit only swap at-most K times and only adjacent swap

user_12405558 0
Viewed 199

I had a test, and there was a problem I still can't solve.
Given an array of numbers, with EACH ELEMENT have at-most K swap allowed, and only adjacent swap, find the largest lexicographical order.
Ex:

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

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

At first I thought it was a modified BubbleSort, but it was not correct, any ideas? Here's the pseudo code:

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 && num[j]<num[j+1]) {
                swap(num[j], num[j+1]);
                swap(table[j], table[j+1]);
                table[j]--;
                table[j+1]--;
            }
}
arrays algorithm c++
2 Answers

You can do with with a max heap of size k+1 initially having the first k+1 values and a hash from each index to the leftmost legal element for that index (disregarding indices <= k).

Then we do the following for each index i in ascending order:

If hash[i] has a value, put it at i and remove it from the heap. If not, move the max elt from the heap to i and remove it from the hash. In either case, add the next elt from the array to the heap.

The hash guarantees that no element moves more than k to the right. The min heap selects the max legal element while guaranteeing that no element moves more than k to the left.

user_20410770

For lexicographical order you have to maximize the first letter, then the 2nd and so on. So you don't need to worry about using swaps on a digit as long as it helps improving the current position (going left to right) and doesn't exceed k. Here is a solution (also modyfing the input like your method):

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 && j - i <= swapsPerElement; j++) {
            if (swaps[j] == swapsPerElement)
                break; // cannot be swapped
            if (num[best] < num[j] && 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;
        }
    }
}
user_47851100
Related