0

当然，在电话采访中我被问到了一个问题，其他问题都很好，但我仍然不确定最佳答案。

起初我认为它闻起来有点基数的味道，但因为你不能只使用相邻的交换，当然不能。

所以我认为它更像是一种冒泡排序类型的算法，这是我试图做的，但“最大交换次数”位让它非常棘手（连同他的词汇部分，但我想这只是一个比较方面的问题）

我想我的算法会是这样的（当然现在我有比面试时更好的想法！）

int index = 0;
while(swapsLeft>0 && index < arrays.length)
{
  int smallestIndex = index;
  for(int i=index; i < index + swapsLeft)
  {
    // of course < is not correct, we need to compare as string or "by radix" or something
    if(array[i]) < array[smallestIndex]
       smallestIndex = i; 
  }
  // if found a smaller item within swap range then swap it to the front
  for(int i = smallestIndex; i > index; i--)
  {
    temp = array[smallestIndex]; 
    array[smallestIndex] = array[index];
    array[index] = temp
    swapsLeft--;
  }
  // continue for next item in array
  index ++; // edit:could probably optimize to index = index + 1 + (smallestIndex - index) ?
}

这看起来对吗？

谁是更好的解决方案，我很好奇一种有效/正确的方法来做到这一点。

4

1 回答 1

0

我实际上正在为我的软件工程学士学位的 Java 算法课程编写这个确切的代码。因此，我将通过解释问题以及解决问题的步骤来帮助您解决这个问题。您将需要至少 2 种方法来多次执行此操作。

首先你取你的第一个值，只是为了让它变得简单，让它保持小而简单。

1 2 3 4

您应该使用数组进行排序。为了从词法上找到下一个数字，你从最右边开始，向左移动，当你发现你的第一个减少时停止。您必须用右边的下一个最大值替换那个较小的值。因此，对于我们的示例，我们将用 4 替换 3。所以我们的下一个数字是：

1 2 4 3

那很简单吧？别担心它会变得更难。现在让我们尝试使用以下方法获取下一个数字：

1 4 3 2

好的，所以我们从最右边开始向左移动直到我们的第一个较小的数字。2小于3 小于4 大于1 1, 3 大于 1，2 大于 1。好的，2 是最后一个数字，这意味着 2 需要替换 1。但是其余的数字呢，它们已经按顺序排列了，它们只是落后于我们需要的东西。所以我们需要翻转订单，我们想出：

2 1 3 4

因此，您需要一个执行该排序的方法，以及另一个在循环中调用该方法的方法，直到您完成正确数量的参数。

于 2014-08-01T14:44:41.163 回答