23

我最近参加了一次面试，被问到这个问题。让我正确解释这个问题：

给定一个数字 M（N 位整数）和 K 个交换操作（交换操作可以交换 2 个数字），设计一种算法来获得最大可能的整数？
示例：
M = 132 K = 1 个输出 = 312
M = 132 K = 2 个输出 = 321
M = 7899 k = 2 个输出 = 9987

我的解决方案（伪代码中的算法）。我使用最大堆在每个 K 操作中从 N 位中获取最大位，然后适当地交换它。 

for(int i = 0; i<K; i++)
{
    int max_digit_currently = GetMaxFromHeap();
    // The above function GetMaxFromHeap() pops out the maximum currently and deletes it from heap

    int index_to_swap_with = GetRightMostOccurenceOfTheDigitObtainedAbove();
    // This returns me the index of the digit obtained in the previous function  
    // .e.g If I have 436659 and K=2 given,   
    // then after K=1 I'll have 936654 and after K=2, I should have 966354 and not 963654.

    // Now, the swap part comes. Here the gotcha is, say with the same above example, I have K=3.
    // If I do GetMaxFromHeap() I'll get 6 when K=3, but I should not swap it, 
    // rather I should continue for next iteration and 
    // get GetMaxFromHeap() to give me 5 and then get 966534 from 966354.

    if (Value_at_index_to_swap == max_digit_currently)
        continue;
    else
        DoSwap();
}

时间复杂度： O(K*( N + log_2(N) ))
// K-times [log_2(N) for pop up number from heap & N to get the most right index to swap with]

上面的策略在这个例子中失败了：
M = 8799 and K = 2
按照我的策略，我会在 K=1 之后得到 M = 9798，在 K=2 之后得到 M = 9978。但是，在 K=2 之后，我能得到的最大值是 M = 9987。

我错过了什么？
还建议其他解决问题的方法和优化我的解决方案的方法。

4

7 回答 7

1

这是一个递归函数，它对每个（当前最大）数字的可能交换值进行排序：

function swap2max(string, K) {
    // the recursion end:
    if (string.length==0 || K==0)
        return string

    m = getMaxDigit(string)
    // an array of indices of the maxdigits to swap in the string
    indices = []
    // a counter for the length of that array, to determine how many chars
    // from the front will be swapped
    len = 0
    // an array of digits to be swapped
    front = []
    // and the index of the last of those:
    right = 0
    // get those indices, in a loop with 2 conditions:
    // * just run backwards through the string, until we meet the swapped range
    // * no more swaps than left (K)
    for (i=string.length; i-->right && len<K;)
        if (m == string[i])
            // omit digits that are already in the right place
            while (right<=i && string[right] == m)
                right++
            // and when they need to be swapped
            if (i>=right)
                front.push(string[right++])
                indices.push(i)
                len++
    // sort the digits to swap with
    front.sort()
    // and swap them
    for (i=0; i<len; i++)
        string.setCharAt(indices[i], front[i])
    // the first len digits are the max ones
    // the rest the result of calling the function on the rest of the string
    return m.repeat(right) + swap2max(string.substr(right), K-len)
}
于 2012-08-29T17:32:31.660 回答
1

我认为缺少的部分是，在您按照 OP 描述的算法执行 K 交换之后，您会留下一些可以在它们之间交换的数字。例如，对于数字 87949，在初始算法之后我们将得到 99748。但是，之后我们可以“免费”交换 7 和 8，即不消耗任何 K 交换。这将意味着“我宁愿不将 7 与第二个 9 交换，而是与第一个交换”。

因此，要获得最大数字，可以执行 OP 描述的算法并记住向右移动的数字以及它们移动到的位置。然后，将这些数字按降序排序，并从左到右放置它们的位置。

这类似于将算法分为两个阶段 - 在第一个阶段中，您选择哪些数字应该放在前面以最大化前 K 个位置。然后，您确定将它们与他们所占据位置的数字交换的顺序，以便数字的其余部分也最大化。

并非所有细节都清楚，我也不是 100% 确定它可以正确处理所有情况，所以如果有人能破解它 - 请继续。

于 2012-08-29T20:42:50.867 回答
0

这是我的方法（它不是万无一失的，但涵盖了基本情况）。首先，我们需要一个将 INT 的每个 DIGIT 提取到容器中的函数：

std::shared_ptr<std::deque<int>> getDigitsOfInt(const int N)
{
    int number(N);
    std::shared_ptr<std::deque<int>> digitsQueue(new std::deque<int>());
    while (number != 0)
    {
        digitsQueue->push_front(number % 10);
        number /= 10;
    }
    return digitsQueue;
}

您显然想要创建与此相反的内容，因此将这样的容器转换回 INT：

const int getIntOfDigits(const std::shared_ptr<std::deque<int>>& digitsQueue)
{
    int number(0);
    for (std::deque<int>::size_type i = 0, iMAX = digitsQueue->size(); i < iMAX; ++i)
    {
        number = number * 10 + digitsQueue->at(i);
    }
    return number;
}

您还需要找到 MAX_DIGIT。使用 std::max_element 会很棒，因为它会将迭代器返回到容器的最大元素，但如果还有更多，您需要最后一个。所以让我们实现我们自己的最大算法：

int getLastMaxDigitOfN(const std::shared_ptr<std::deque<int>>& digitsQueue, int startPosition)
{
    assert(!digitsQueue->empty() && digitsQueue->size() > startPosition);
    int maxDigitPosition(0);
    int maxDigit(digitsQueue->at(startPosition));
    for (std::deque<int>::size_type i = startPosition, iMAX = digitsQueue->size(); i < iMAX; ++i)
    {
        const int currentDigit(digitsQueue->at(i));

        if (maxDigit <= currentDigit)
        {
            maxDigit = currentDigit;
            maxDigitPosition = i;
        }
    }
    return maxDigitPosition;
}

从这里开始，您必须做的事情非常简单，将最右边（最后一个）MAX DIGITS 放在他们的位置，直到您可以交换：

const int solution(const int N, const int K)
{
    std::shared_ptr<std::deque<int>> digitsOfN = getDigitsOfInt(N);

    int pos(0);
    int RemainingSwaps(K);
    while (RemainingSwaps)
    {
        int lastHDPosition = getLastMaxDigitOfN(digitsOfN, pos);
        if (lastHDPosition != pos)
        {
            std::swap<int>(digitsOfN->at(lastHDPosition), digitsOfN->at(pos));

            ++pos;
            --RemainingSwaps;
        }
    }

    return getIntOfDigits(digitsOfN);
}

有未处理的极端情况，但我会留给你。

于 2014-10-04T13:52:06.663 回答
0

这都是伪代码，但很容易转换为其他语言。该解决方案是非递归的，并且在线性最坏情况和平均情况时间下运行。

为您提供以下功能：

function k_swap(n, k1, k2):
    temp = n[k1]
    n[k1] = n[k2]
    n[k2] = temp

int : operator[k]
    // gets or sets the kth digit of an integer

property int : magnitude
    // the number of digits in an integer

您可以执行以下操作：

int input = [some integer] // input value

int digitcounts[10] = {0, ...} // all zeroes
int digitpositions[10] = {0, ...) // all zeroes
bool filled[input.magnitude] = {false, ...) // all falses

for d = input[i = 0 => input.magnitude]:
    digitcounts[d]++ // count number of occurrences of each digit

digitpositions[0] = 0;
for i = 1 => input.magnitude:
    digitpositions[i] = digitpositions[i - 1] + digitcounts[i - 1] // output positions

for i = 0 => input.magnitude:
    digit = input[i]
    if filled[i] == true:
        continue
    k_swap(input, i, digitpositions[digit])
    filled[digitpositions[digit]] = true
    digitpositions[digit]++

我会用数字走过它input = 724886771

computed digitcounts:
{0, 1, 1, 0, 1, 0, 1, 3, 2, 0}

computed digitpositions:
{0, 0, 1, 2, 2, 3, 3, 4, 7, 9}

swap steps:
swap 0 with 0: 724886771, mark 0 visited
swap 1 with 4: 724876781, mark 4 visited
swap 2 with 5: 724778881, mark 5 visited
swap 3 with 3: 724778881, mark 3 visited
skip 4 (already visited)
skip 5 (already visited)
swap 6 with 2: 728776481, mark 2 visited
swap 7 with 1: 788776421, mark 1 visited
swap 8 with 6: 887776421, mark 6 visited

output number: 887776421

编辑：

这没有正确解决问题。如果我以后有时间，我会修复它，但我现在没有。

于 2012-08-29T17:53:19.067 回答
0

假设传递了一个幻想整数数组，其中每个元素代表一个十进制数字，我会怎么做（在伪 C 中——没什么特别的）：

int[] sortToMaxInt(int[] M, int K) {
    for (int i = 0; K > 0 && i < M.size() - 1; i++) {
        if (swapDec(M, i)) K--;
    }
    return M;
}

bool swapDec(int[]& M, int i) {
    /* no need to try and swap the value 9 as it is the 
     * highest possible value anyway. */
    if (M[i] == 9) return false;

    int max_dec = 0;
    int max_idx = 0;
    for (int j = i+1; j < M.size(); j++) {
        if (M[j] >= max_dec) {
            max_idx = j;
            max_dec = M[j];
        }
    }

    if (max_dec > M[i]) {
        M.swapElements(i, max_idx);
        return true;
    }
    return false;
}

从我的头顶，所以如果有人发现一些致命的缺陷，请告诉我。

编辑：根据此处发布的其他答案，我可能严重误解了这个问题。有人愿意详细说明吗？

于 2012-08-29T18:15:45.013 回答
0

你从max-number(M, N, 1, K).

max-number(M, N, pos, k)
{
    if k == 0
        return M
    max-digit = 0
    for i = pos to N
        if M[i] > max-digit
            max-digit = M[i]
    if M[pos] == max-digit
        return max-number(M, N, pos + 1, k)
    for i = (pos + 1) to N
        maxs.add(M)
        if M[i] == max-digit
            M2 = new M
            swap(M2, i, pos)
            maxs.add(max-number(M2, N, pos + 1, k - 1))
    return maxs.max()
}
于 2012-08-29T18:47:53.290 回答
0

我假设 K = 2，但你可以改变这个值！

Java 代码

public class Solution {
    public static void main (String args[]) {
        Solution d = new Solution();
        System.out.println(d.solve(1234));
        System.out.println(d.solve(9812));
        System.out.println(d.solve(9876));
    }
    public int solve(int number) {
        int[] array = intToArray(number);
        int[] result = solve(array, array.length-1, 2);
        return arrayToInt(result);
    }
    private int arrayToInt(int[] array) {
        String s = "";
        for (int i = array.length-1 ;i >= 0; i--) {
            s = s + array[i]+"";
        }
        return Integer.parseInt(s);
    }
    private int[] intToArray(int number){
        String s = number+"";
        int[] result = new int[s.length()];
        for(int i = 0 ;i < s.length() ;i++) {
            result[s.length()-1-i] = Integer.parseInt(s.charAt(i)+"");
        }
        return result;
    }
    private int[] solve(int[] array, int endIndex, int num) {
        if (endIndex == 0)
            return array;
        int size = num ;
        int firstIndex = endIndex - size;
        if (firstIndex < 0)
            firstIndex = 0;
        int biggest = findBiggestIndex(array, endIndex, firstIndex);
        if (biggest!= endIndex) {
            if (endIndex-biggest==num) {
                while(num!=0) {
                    int temp = array[biggest];
                    array[biggest] = array[biggest+1];
                    array[biggest+1] = temp;
                    biggest++;
                    num--;
                }
                return array;
            }else{
                int n = endIndex-biggest;
                for (int i = 0 ;i < n;i++) {
                    int temp = array[biggest];
                    array[biggest] = array[biggest+1];
                    array[biggest+1] = temp;
                    biggest++;
                }
                return solve(array, --biggest, firstIndex);
            }
        }else{
            return solve(array, --endIndex, num);
        }
    }
    private int findBiggestIndex(int[] array, int endIndex, int firstIndex) {
        int result = firstIndex;
        int max = array[firstIndex];
        for (int i = firstIndex; i <= endIndex; i++){
            if (array[i] > max){
                max = array[i];
                result = i;
            }
        }
        return result;
    }
}
于 2017-08-16T22:29:53.130 回答