使和最小的唯一数组
这是一个面试问题。给定一个数组，例如3,2,1,2,7，我们希望通过增加重复元素来使该数组中的所有元素都是唯一的，并且我们要求精化后的数组的和是最小的。例如，3,2,1,2,7的答案是3,2,1,4,7，它的总和是17。有什么想法吗？
回答 4
Stack Overflow用户
发布于 2017-10-08 20:43:27
它并不像我之前提到的那么简单，但也不是非常复杂。
首先，对输入数组进行排序。如果能够恢复元素的原始顺序很重要，那么记录用于排序的排列。
其次，从左到右(即从低到高)扫描排序后的数组。如果某个元素小于或等于其左侧的元素，则将其设置为比该元素大1。
伪码
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结果的和是最小的吗？我已经说服自己，这是通过一些挠头和试验，但我没有正式的证据。
Stack Overflow用户
发布于 2017-10-08 18:26:56
如果你只需要找到一个最好的解决方案，这里有一些解释的算法。这个问题的想法是找到一个最佳解决方案，只有通过测试所有现有的解决方案才能找到它(好吧，它们是无限的，让我们坚持使用合理的解决方案)。
我用C语言写了一个程序，因为我对它很熟悉，但是你可以把它移植到你想要的任何语言上。
程序这样做:它尝试将一个值递增到可能的最大值(我将在代码部分的注释中解释如何找到它)，如果找不到解决方案，则减少该值并继续下一个值，依此类推。
这是一种指数算法，因此它在处理大量重复数据时会非常慢(但它可以确保找到最佳解决方案)。
我用您的示例测试了这段代码，它工作正常；不确定是否有任何bug，但代码(用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为了便于理解，我做了一些typedefs。别担心。
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。然后，还有我们将在后面禁用的主函数。check函数只检查临时解决方案中是否有重复的值。
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;
}我希望这是有用的。如果有什么不清楚的地方，请写下来。
Stack Overflow用户
发布于 2018-04-19 02:24:45
我在一次面试中也被问到了同样的问题。不确定你是否还需要它。但这就是我是如何做到的。它工作得很好。
num_list1 = [2,8,3,6,3,5,3,5,9,4]
def UniqueMinSumArray(num_list):
max=min(num_list)
for i,V in enumerate(num_list):
while (num_list.count(num_list[i])>1):
if (max > num_list[i]+1) :
num_list[i] = max + 1
else:
num_list[i]+=1
max = num_list[i]
i+=1
return num_list
print (sum(UniqueMinSumArray(num_list1)))你可以尝试你的数字列表，我相信它会给你正确的唯一的最小和。
https://stackoverflow.com/questions/46629061
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号