1

我最近在一次采访中遇到了这个问题，我很好奇解决它的最佳方法是什么。问题是一个 char 数组，它具有 ascii 字符 '0' 到 '9' 进行一次交换，使得结果数组中的 ascii 值集形成可能的最低值。两个输入数组都没有前面的 0，结果数组也没有。

所以这里有一个例子：char a[] = {'1','0', '9','7','6'}

解决方案：char b[] = { '1','0', '6', '7', '9'}

另一个例子：char a[] = {'9','0', '7','6','1'}

解决方案： char b[] = {'1','0', '7','6','9'}

我正在寻找性能方面的最佳解决方案。由于只允许一次交换，我假设不允许排序。我没有澄清这一点。因此，我们正在寻找仅通过一次交换即可获得的最低值。如果您也可以提供解决方案的复杂性，那将会有所帮助。

4

4 回答 4

1

算法：

请注意，由于不能有前导 0，因此应单独处理 0。

从右边开始，跟踪最小的非零数。还要记录第一个 0。

每当您发现一个大于记录的非零数字的数字时，将这 2 个记录为迄今为止最好的交换。

找到零后，从此处记录任何非零非前导字符作为零的最佳交换。

请注意，您没有对上述任何一种交换的质量进行任何比较，我们只是用新的替换当前最好的，因为用更靠左的位置交换总是更好。

完成后，比较零的最佳交换的目标位置和非零的最佳交换的目标位置，然后选择最左边的位置，或者如果它们相同，则选择零。

如果没有找到可能的交换，则数组已经是给定数字的最小排列，因此不要做任何事情。或者，如果必须，交换最右边的两个字符。

运行时间：

O(n).

例子：

输入： 10976

Processing  6   7   9   0   1
Minimum     6   6   6   6   1
Best swap   -   6+7 6+9 6+9 6+9
Zero?       No  No  No  Yes Yes
Best 0 swap -   -   -   -   -

所以最好的交换是 6/9，给我们 10679

输入： 3601

Processing  1   0   6   3
Minimum     1   1   1   3
Best swap   -   -   1+6 1+3
Zero?       No  Yes Yes Yes
Best 0 swap -   -   0+6 0+6

这里可能的交换是 1/3 和 0/6。
对于 1/3 交换，目标位置为 0（0 索引）。
对于 0/6 掉期，目标位置是 1。
所以我们选择 1/3 掉期给我们 1603。

于 2013-10-02T08:36:47.280 回答
0

我认为您显然必须至少遍历一次数组。您需要这样做才能找到最小值。

您还需要找到满足条件的值。海报说输入数组不会以'0'作为前导元素。

我们一次遍历一个位置的数组。我们正在寻找另一个具有最小值（第一个点非零，其他点为任何值）且小于任何其他位置的位置。 

for (pos = 0; pos < array_size-1; pos++) {
        low_index = pos;
        min_value = (pos == 0) ? '1' : '0';

        for (i = pos+1; i < array_size; i++) {
                if (min_value <= array[i]) && (array[i] < array[low_index])) {
                        low_index = i;
                }
        }

        if (low_index != pos) {
                low_value = array[pos];
                array[pos] = array[low_index];
                array[low_index] = low_value;
                break;
        }
}
于 2013-10-01T21:58:34.430 回答
0 
Start at the leftmost digit

While current digit is valued the lowest (non-zero for the first digits equal 
  to the number of zeroes in the set) of the remaining set of numbers, advance
  to the next number

Swap current value with lowest remaining value.

您可以保留数组的排序副本，以帮助您进行决策。您需要它来了解您当前的最低数字有多少。如果您也存储它们的索引，则可以使其更加高效。

没有必要拥有任何额外的存储空间，但它可能会使事情变得更快。在第一个数组的单次传递中，您可以获得 0 的数量以及下一个最小数字的索引，但是在像 1、0、6、9、7 这样的数组中，您必须通过阵列4个不同的时间。

编辑 - 稍微更多的冲洗算法

Copy the array into a separate one, called c, and sort c.  (You'll use this to make your decision faster, though you could simply repeatedly analyze the array.)
if c has zeros, find the value of its first non-zero value, called x
if a[0] != x, swap a[0] with x.
set index to 1
while a[index] == c[index], ++index
swap a[index] with c[index]

如果你这样做，它会花费你另一个数组，但是通过一次排序和一次通过数组来完成。

如果您不这样做，则每次都必须通过数组的其余部分才能找到最小值。我不擅长复杂性，但我相信这是 n log n，因为每次迭代都会从更高的索引开始。

如果不使用数组，您必须执行类似的操作

Find the lowest non-zero value
if a[0] isn't this value, swap with this value
index = 1
find lowest value starting at a[index]
if they're not equal, swap the values, done.  Otherwise,  increment index

那仍然是 n log n。我认为排序可以提高效率。

于 2013-10-01T21:38:31.410 回答
0

取决于你所说的最好是什么意思。取出除'0'外的最小数作为b中的第一项，然后将其余的按升序排序。

于 2013-10-01T21:39:58.207 回答