最小配列で一意の配列を作る

Question

面接問題です。例えば[3,2,1,2,7]のような配列が与えられた場合、この配列のすべての要素を重複する要素を増分することによってユニークにする必要があり、洗練された配列の合計が最小であることが必要です。たとえば[3,2,1,2,7]の回答は[3,2,1,4,7]であり、その合計は17です。

Answer 1

最高の解決策の1つを見つける必要がある場合は、ここでいくつかの説明と一緒にalgorythmです。 この問題のアイデアは、すべての既存のソリューションをテストすることによってしか見つけられない最適なソリューションを見つけることです（無限で、合理的なソリューションに固執してください）。

私はそれに精通しているので、私はCでプログラムを書いたが、必要な言語に移植することができます。

プログラムはこれを行います：可能な限り1つの値を増やそうとします（コードセクションのコメントの中で見つける方法を説明します）。解決策が見つからない場合よりも、この値を減らして行く次のものと順番にやって来る。

これは指数関数的なものであるため、重複したデータの値が大きい場合は非常に遅くなります（しかし、最良の解決策が見つかることを保証します）。

私はあなたの例でこのコードをテストしました。バグが残っているかどうかは分かりませんが、コードは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を使いました。心配しないでください。

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 
} 

これは再帰関数です。最初に解決策がOKかどうか、それが今までに見つかった最良の解決策であるかどうかがチェックされます。そして、すべてが正しければ、実際の解を一時的な値で更新し、最適条件を更新する。 次に、反復する各値（ifは他のインデックスを除外します）を繰り返して、最悪の場合のシナリオに達するまで再帰的に進みます。チェック条件は最大値を超えて満たされません。 それから、私たちはバックトラックして、反復を続行しなければなりません。それは他の値と続くでしょう。

PS：最適条件をチェックから次の条件に移動すると、最適化が可能です。ソリューションが既に最適でない場合は、追加するだけで最適なものを見つけることはできません。

ハードコードは終了しました、そしてサポートする機能があります。

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

私の以前のコメントが示唆しているほど単純ではありませんが、それほど複雑ではありません。

まず、入力配列をソートします。要素の元の順序を復元できることが重要な場合は、並べ替えに使用された順列を記録します。

第2に、並べ替えられた配列を左から右（つまり、低から高）までスキャンします。要素が左の要素以下の場合は、その要素より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 

は結果最小限の合計ですか？私はそれがいくつかの頭を掻くことと試練であると自分自身に確信しましたが、私は正式な証拠を持っていません。