用最小的金额制作独特的排列

Question

这是一个面试问题。给定一个数组，例如[3,2,1,2,7]，我们希望通过递增重复元素来使该数组中的所有元素都是唯一的，并且我们要求精修数组的总和最小。例如，[3,2,1,2,7]的答案是[3,2,1,4,7]，其总和是17.任何想法？

Answer 1

如果你只需要找到最好的解决方案之一，这里的algorythm与一些解释。 这个问题的想法是找到一个最佳的解决方案，只有通过测试所有现有的解决方案才能找到最佳的解决方案（好吧，它们是无限的，让我们坚持合理的解决方案）。

我用C编写了一个程序，因为我很熟悉它，但是你可以把它移植到你想要的任何语言。

该程序执行此操作：它会尝试将一个值增加到最大值（我将解释如何在代码段中的注释中找到它），比找不到该解决方案时减少该值并去与下一个等等。

这是一个指数函数，所以对于大数据量的重复数据将会非常缓慢（但它确保找到最佳解决方案）。

我用你的例子测试了这段代码，不确定是否还有任何错误，但代码（在C中）是这样的。

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
typedef int BOOL; //just to ease meanings of values 
#define TRUE 1 
#define FALSE 0 

为了便于理解，我做了一些类型定义。别担心。

typedef struct duplicate {  //used to fasten the algorythm; it uses some more memory just to assure it's ok 
    int value; 
    BOOL duplicate; 
} duplicate_t; 

int maxInArrayExcept(int *array, int arraySize, int index); //find the max value in array except the value at the index given 
                  //the result is the max value in the array, not counting th index 
int *findDuplicateSum(int *array, int arraySize); 
BOOL findDuplicateSum_R(duplicate_t *array, int arraySize, int *tempSolution, int *solution, int *totalSum, int currentSum); //resursive function used to find solution 
BOOL check(int *array, int arraySize); //checks if there's any repeated value in the solution 

这些都是我们需要的所有功能。所有分手为理解目的。 首先，我们有一个结构。该结构用于避免在每次迭代时检查给定索引上的值是否最初是重复的。我们不想修改任何原来不重复的值。然后，我们有几个功能：首先，我们需要看到最坏的情况：重复后的每个值都已被占用：然后我们需要将重复值增加到最大值达到+ 1。然后，我们稍后会讨论主函数。 检查功能只检查临时解决方案中是否有任何重复值。

int main() {       //testing purpose 
    int i; 
    int testArray[] = { 3,2,1,2,7 }; //test array 
    int nTestArraySize = 5;    //test array size 
    int *solutionArray;     //needed if you want to use the solution later 
    solutionArray = findDuplicateSum(testArray, nTestArraySize); 
    for (i = 0; i < nTestArraySize; ++i) { 
     printf("%d ", solutionArray[i]); 
    } 
    return 0; 
} 

这是主要的功能：我用它来测试一切。

int * findDuplicateSum(int * array, int arraySize) 
{ 
    int *solution = malloc(sizeof(int) * arraySize); 
    int *tempSolution = malloc(sizeof(int) * arraySize); 
    duplicate_t *duplicate = calloc(arraySize, sizeof(duplicate_t)); 
    int i, j, currentSum = 0, totalSum = INT_MAX; 
    for (i = 0; i < arraySize; ++i) { 
     tempSolution[i] = solution[i] = duplicate[i].value = array[i]; 
     currentSum += array[i]; 
     for (j = 0; j < i; ++j) { //to find ALL the best solutions, we should also put the first found value as true; it's just a line more 
           //yet, it saves the algorythm half of the duplicated numbers (best/this case scenario) 
      if (array[j] == duplicate[i].value) { 
       duplicate[i].duplicate = TRUE; 
      } 
     } 
    } 
    if (findDuplicateSum_R(duplicate, arraySize, tempSolution, solution, &totalSum, currentSum)); 
    else { 
     printf("No solution found\n"); 
    } 
    free(tempSolution); 
    free(duplicate); 
    return solution; 
} 

这个功能做了很多事情：第一，它建立了解决方案阵列，然后将其初始化这两个解决方案值和重复的阵列，用来启动时检查重复值的一个。然后，我们找到当前总和，并将最大可用总和设置为可能的最大整数。 然后，调用递归函数;这个给了我们有关找到解决方案（应该总是）的信息，然后我们将解决方案作为数组返回。

int findDuplicateSum_R(duplicate_t * array, int arraySize, int * tempSolution, int * solution, int * totalSum, int currentSum) 
{ 
    int i; 
    if (check(tempSolution, arraySize)) { 
     if (currentSum < *totalSum) {  //optimal solution checking 
      for (i = 0; i < arraySize; ++i) { 
       solution[i] = tempSolution[i]; 
      } 
      *totalSum = currentSum; 
     } 
     return TRUE; //just to ensure a solution is found 
    } 
    for (i = 0; i < arraySize; ++i) { 
     if (array[i].duplicate == TRUE) { 
      if (array[i].duplicate <= maxInArrayExcept(solution, arraySize, i)) { //worst case scenario, you need it to stop the recursion on that value 
       tempSolution[i]++; 
       return findDuplicateSum_R(array, arraySize, tempSolution, solution, totalSum, currentSum + 1); 
       tempSolution[i]--; //backtracking 
      } 
     } 
    } 
    return FALSE; //just in case the solution is not found, but we won't need it 
} 

这是递归函数。它首先检查解决方案是否正常，以及是否是迄今为止找到的最好解决方案。然后，如果一切正确，它将使用临时值更新实际解决方案，并更新最佳条件。 然后，我们迭代每个重复的值（if排除其他索引），然后我们继续递归，直到（如果不幸）我们达到最坏的情况：检查条件不满足最大值。 然后我们必须回溯并继续迭代，这将继续与其他值。

PS：如果我们将最优条件从检查移动到for：如果解决方案已经不是最优的，我们不能指望找到更好的方法来添加内容。

硬代码已经结束，并有配套功能：

int maxInArrayExcept(int *array, int arraySize, int index) { 
    int i, max = 0; 
    for (i = 0; i < arraySize; ++i) { 
     if (i != index) { 
      if (array[i] > max) { 
       max = array[i]; 
      } 
     } 
    } 
    return max; 
} 

BOOL check(int *array, int arraySize) { 
    int i, j; 
    for (i = 0; i < arraySize; ++i) { 
     for (j = 0; j < i; ++j) { 
      if (array[i] == array[j]) return FALSE; 
     } 
    } 
    return TRUE; 
} 

我希望这是有益的。 如果有任何不清楚的地方，请写下。

Answer 2

这并不像我之前的评论中提到的那么简单，但它并不复杂。

首先，对输入数组进行排序。如果重要的是能够恢复元素的原始顺序，则记录用于排序的排列。

其次，从左到右（即从低到高）扫描排序后的数组。如果元素小于或等于其左侧的元素，则将其设置为大于该元素的一个元素。

伪

sar = sort(input_array) 
    for index = 2:size(sar) ! I count from 1 
     if sar(index)<=sar(index-1) sar(index) = sar(index-1)+1 
    forend 

是结果最小的总和？我已经相信自己，这是通过一些头部抓挠和试验，但我没有得到正式的证据。