この問題は、Microsoftへのインタビューから得たものです。
ランダムな整数の配列が与えられた場合、重複した数値を削除し、元の配列の一意の数値を返すアルゴリズムをCで記述します。
例：入力：{4, 8, 4, 1, 1, 2, 9} 出力：{4, 8, 1, 2, 9, ?, ?}
注意点の1つは、期待されるアルゴリズムでは、配列を最初にソートする必要がないことです。また、要素が削除された場合は、次の要素も前方にシフトする必要があります。とにかく、要素が前方にシフトされた配列の末尾にある要素の値は無視できます。
更新：結果は元の配列で返される必要があり、ヘルパーデータ構造（ハッシュテーブルなど）は使用しないでください。ただし、注文の保存は必要ないと思います。
Update2：なぜこれらの非現実的な制約があるのか疑問に思う人のために、これはインタビューの質問でした。これらの制約はすべて、思考プロセス中に議論され、さまざまなアイデアを思いつく方法を確認します。
私のガールフレンドによって提案された解決策は、マージソートのバリエーションです。唯一の変更は、マージステップ中に、重複した値を無視することです。このソリューションもO（n log n）になります。このアプローチでは、ソート/重複の削除が組み合わされます。しかし、それが何か違いを生むかどうかはわかりません。
これは以前にSOに投稿したことがありますが、かなりかっこいいのでここで再現します。ハッシュを使用して、ハッシュセットのようなものを適切に構築します。腋窩空間ではO（1）であることが保証されており（再帰は末尾呼び出しです）、通常はO（N）時間計算量です。アルゴリズムは次のとおりです。
これは、ハッシュに病理学的シナリオがない場合、O（N）であると示すことができます。重複がない場合でも、各再帰で要素の約2/3が削除されます。再帰の各レベルはO（n）です。ここで、小さいnは残っている要素の量です。唯一の問題は、実際には、重複が少ない場合、つまり衝突が多い場合、クイックソートよりも遅いということです。ただし、重複が大量にある場合は、驚くほど高速です。
編集：Dの現在の実装では、hash_tは32ビットです。このアルゴリズムに関するすべてのことは、完全な32ビット空間でのハッシュ衝突があったとしてもごくわずかであることを前提としています。ただし、衝突はモジュラス空間で頻繁に発生する可能性があります。ただし、この仮定は、合理的なサイズのデータセットにはおそらく当てはまります。キーが32ビット以下の場合、それはそれ自体のハッシュである可能性があります。つまり、完全な32ビット空間での衝突は不可能です。それが大きい場合、問題になるのに十分な数を32ビットメモリアドレス空間に収めることができません。データセットが大きくなる可能性があるDの64ビット実装では、hash_tが64ビットに増加すると想定しています。さらに、これが問題であることが判明した場合は、再帰の各レベルでハッシュ関数を変更できます。
Dプログラミング言語での実装は次のとおりです。
void uniqueInPlace(T)(ref T[] dataIn) {
uniqueInPlaceImpl(dataIn, 0);
}
void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
if(dataIn.length - start < 2)
return;
invariant T sentinel = dataIn[start];
T[] data = dataIn[start + 1..$];
static hash_t getHash(T elem) {
static if(is(T == uint) || is(T == int)) {
return cast(hash_t) elem;
} else static if(__traits(compiles, elem.toHash)) {
return elem.toHash;
} else {
static auto ti = typeid(typeof(elem));
return ti.getHash(&elem);
}
}
for(size_t index = 0; index < data.length;) {
if(data[index] == sentinel) {
index++;
continue;
}
auto hash = getHash(data[index]) % data.length;
if(index == hash) {
index++;
continue;
}
if(data[index] == data[hash]) {
data[index] = sentinel;
index++;
continue;
}
if(data[hash] == sentinel) {
swap(data[hash], data[index]);
index++;
continue;
}
auto hashHash = getHash(data[hash]) % data.length;
if(hashHash != hash) {
swap(data[index], data[hash]);
if(hash < index)
index++;
} else {
index++;
}
}
size_t swapPos = 0;
foreach(i; 0..data.length) {
if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
swap(data[i], data[swapPos++]);
}
}
size_t sentinelPos = data.length;
for(size_t i = swapPos; i < sentinelPos;) {
if(data[i] == sentinel) {
swap(data[i], data[--sentinelPos]);
} else {
i++;
}
}
dataIn = dataIn[0..sentinelPos + start + 1];
uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}
優れたO表記を探している場合は、配列をO（n log n）ソートでソートしてから、O（n）トラバーサルを実行するのが最適なルートです。ソートせずに、O（n ^ 2）を見ています。
編集：整数を実行しているだけの場合は、基数ソートを実行してO（n）を取得することもできます。
どうですか：
void rmdup(int *array, int length)
{
int *current , *end = array + length - 1;
for ( current = array + 1; array < end; array++, current = array + 1 )
{
while ( current <= end )
{
if ( *current == *array )
{
*current = *end--;
}
else
{
current++;
}
}
}
}
O（n ^ 2）以下である必要があります。
もう1つの効率的な実装
int i, j;
/* new length of modified array */
int NewLength = 1;
for(i=1; i< Length; i++){
for(j=0; j< NewLength ; j++)
{
if(array[i] == array[j])
break;
}
/* if none of the values in index[0..j] of array is not same as array[i],
then copy the current value to corresponding new position in array */
if (j==NewLength )
array[NewLength++] = array[i];
}
この実装では、配列をソートする必要はありません。また、重複する要素が見つかった場合、この後のすべての要素を1つの位置だけシフトする必要はありません。
このコードの出力は、サイズがNewLengthのarray[]です。
ここでは、配列の2番目の要素から開始し、この配列までの配列のすべての要素と比較しています。入力配列を変更するための追加のインデックス変数「NewLength」を保持しています。NewLengthvariabelは0に初期化されます。
array[1]の要素はarray[0]と比較されます。それらが異なる場合、array[NewLength]の値はarray[1]で変更され、NewLengthが増分されます。それらが同じである場合、NewLengthは変更されません。
したがって、配列[1 2 1 3 1]がある場合、
'j'ループの最初のパスでは、array [1]（2）がarray0と比較され、次に2がarray [NewLength] = array [1]に書き込まれるため、NewLength = 2であるため、arrayは[12]になります。
'j'ループの2番目のパスでは、array [2]（1）がarray0およびarray1と比較されます。ここでは、array [2]（1）とarray0が同じであるため、ここでループが中断されます。NewLength = 2なので、配列は[12]になります
等々
1. O（1）余分なスペースをO（n log n）時間で使用する
これは、たとえば次のように可能です。
ejelのパートナーは正しいと思います。これを行うための最良の方法は、単純化されたマージステップを使用したインプレースマージソートであり、たとえば、あなたがそうであれば、それがおそらく質問の意図です。入力を改善する機能なしでこれを可能な限り効率的に行うための新しいライブラリ関数を作成します。入力の種類によっては、ハッシュテーブルなしでこれを行うと便利な場合があります。しかし、私は実際にこれをチェックしていません。
2. O（lots）の余分なスペースをO（n）時間で使用する
これは、いくつかの疑わしい仮定が成り立つ場合にのみ機能します。
悪い答えですが、入力要素がたくさんあるが、それらがすべて8ビット整数（または16ビット整数）である場合は、それが最善の方法である可能性があります。
3. O（少し）っぽい余分なスペース、O（n）っぽい時間
＃2と同じですが、ハッシュテーブルを使用します。
4.明確な方法
要素の数が少ない場合、他のコードの記述が速く、読み取りが速い場合、適切なアルゴリズムを記述することは役に立ちません。
例えば。一意の要素（つまり、最初の要素、2番目の要素（最初の要素の複製が削除されている）など）ごとに配列をウォークスルーして、すべての同一の要素を削除します。O（1）余分なスペース、O（n ^ 2）時間。
例えば。これを行うライブラリ関数を使用します。効率は、どちらを簡単に利用できるかによって異なります。
まあ、それは基本的な実装は非常に簡単です。すべての要素を調べ、残りの要素に重複があるかどうかを確認し、残りをそれらの上に移動します。
それはひどく非効率的であり、出力またはソート/バイナリツリーのヘルパー配列によってスピードアップすることができますが、これは許可されていないようです。
記憶を犠牲にすることをいとわないのであれば、これを1回のトラバーサルで行うことができます。ハッシュ/連想配列で整数を見たかどうかを簡単に集計できます。すでに番号を見ている場合は、移動しながら削除するか、見たことのない番号を新しい配列に移動して、元の配列でのシフトを回避します。
Perlの場合：
foreach $i (@myary) {
if(!defined $seen{$i}) {
$seen{$i} = 1;
push @newary, $i;
}
}
C ++の使用が許可されている場合は、toをstd::sort呼び出してからtoを呼び出すとstd::unique、答えが得られます。時間計算量は、ソートの場合はO（N log N）、一意のトラバーサルの場合はO（N）です。
そして、C ++がテーブルから外れている場合、これらの同じアルゴリズムがCで記述されるのを妨げるものは何もありません。
関数の戻り値は一意の要素の数である必要があり、それらはすべて配列の先頭に格納されます。この追加情報がないと、重複があったかどうかさえわかりません。
外側のループが繰り返されるたびに、配列の1つの要素が処理されます。一意の場合は配列の先頭に残り、重複している場合は、配列内の最後の未処理の要素によって上書きされます。このソリューションはO（n ^ 2）時間で実行されます。
#include <stdio.h>
#include <stdlib.h>
size_t rmdup(int *arr, size_t len)
{
size_t prev = 0;
size_t curr = 1;
size_t last = len - 1;
while (curr <= last) {
for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
if (prev == curr) {
++curr;
} else {
arr[curr] = arr[last];
--last;
}
}
return curr;
}
void print_array(int *arr, size_t len)
{
printf("{");
size_t curr = 0;
for (curr = 0; curr < len; ++curr) {
if (curr > 0) printf(", ");
printf("%d", arr[curr]);
}
printf("}");
}
int main()
{
int arr[] = {4, 8, 4, 1, 1, 2, 9};
printf("Before: ");
size_t len = sizeof (arr) / sizeof (arr[0]);
print_array(arr, len);
len = rmdup(arr, len);
printf("\nAfter: ");
print_array(arr, len);
printf("\n");
return 0;
}
これがJavaバージョンです。
int[] removeDuplicate(int[] input){
int arrayLen = input.length;
for(int i=0;i<arrayLen;i++){
for(int j = i+1; j< arrayLen ; j++){
if(((input[i]^input[j]) == 0)){
input[j] = 0;
}
if((input[j]==0) && j<arrayLen-1){
input[j] = input[j+1];
input[j+1] = 0;
}
}
}
return input;
}
これが私の解決策です。
///// find duplicates in an array and remove them
void unique(int* input, int n)
{
merge_sort(input, 0, n) ;
int prev = 0 ;
for(int i = 1 ; i < n ; i++)
{
if(input[i] != input[prev])
if(prev < i-1)
input[prev++] = input[i] ;
}
}
値の不必要な前後のコピーを避けるために、配列は明らかに右から左に「トラバース」する必要があります。
無制限のメモリがある場合は、sizeof(type-of-element-in-array) / 8バイトにビット配列を割り当てて、対応する値に既に遭遇したかどうかを各ビットに示すことができます。
そうでない場合は、配列を走査して各値をそれに続く値と比較し、重複が見つかった場合はこれらの値を完全に削除することほど良いことは考えられません。これは、 O（n ^ 2）（またはO（（n ^ 2-n）/ 2） ）の近くにあります。
IBMには、ちょっと近いテーマに関する記事があります。
どれどれ：
これは、O（N log N）アルゴリズムを使用し、追加のストレージなしで1回のパスで実行できます。
a[1]要素からに進みa[N]ます。各段階iで、左側のすべての要素は、までの要素a[i]のソートされたヒープを構成a[0]しa[j]ます。一方、2番目のインデックスj（最初は0）は、ヒープのサイズを追跡します。
調べa[i]て、ヒープに挿入します。ヒープは、の要素a[0]を占有しa[j+1]ます。要素が挿入されるときに、同じ値を持つ重複要素が見つかった場合は、ヒープにa[k]挿入しないでください（つまり、破棄します）。a[i]それ以外の場合は、ヒープに挿入します。ヒープは1要素ずつ増加し、 a[0]toa[j+1]とincrementで構成されますj。
この方法で続行し、iすべての配列要素が調べられてヒープに挿入されるまでインクリメントa[0]します。これにより、が。になりa[j]ます。jはヒープの最後の要素のインデックスであり、ヒープには一意の要素値のみが含まれます。
int algorithm(int[] a, int n)
{
int i, j;
for (j = 0, i = 1; i < n; i++)
{
// Insert a[i] into the heap a[0...j]
if (heapInsert(a, j, a[i]))
j++;
}
return j;
}
bool heapInsert(a[], int n, int val)
{
// Insert val into heap a[0...n]
...code omitted for brevity...
if (duplicate element a[k] == val)
return false;
a[k] = val;
return true;
}
例を見ると、結果の配列は元の要素の順序を保持しているため、これは正確には要求されたものではありません。ただし、この要件が緩和されている場合は、上記のアルゴリズムでうまくいくはずです。
Javaではこのように解決します。これをCで書く方法がわからない。
int length = array.length;
for (int i = 0; i < length; i++)
{
for (int j = i + 1; j < length; j++)
{
if (array[i] == array[j])
{
int k, j;
for (k = j + 1, l = j; k < length; k++, l++)
{
if (array[k] != array[i])
{
array[l] = array[k];
}
else
{
l--;
}
}
length = l;
}
}
}
次はどうですか？
int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
for(y=0;y<count;y++)
{
if(*(temp+y)==*(array+x))
{
break;
}
}
if(y==count)
{
*(temp+count) = *(array+x);
count++;
}
}
memcpy(array, temp, sizeof(int)*len);
すべてを元の配列にコピーして戻す前に、一時配列を宣言して要素をその中に入れようとします。
問題を確認した後、これが私のデルフィーウェイです。
var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;
for I := 0 to C-1 do
begin
for J := I+1 to C-1 do
if A[I]=A[J] then
begin
for K := C-1 Downto J do
if A[J]<>A[k] then
begin
P:=A[K];
A[K]:=0;
A[J]:=P;
C:=K;
break;
end
else
begin
A[K]:=0;
C:=K;
end;
end;
end;
//tructate array
setlength(A,C);
end;
次の例で問題を解決できます。
def check_dump(x):
if not x in t:
t.append(x)
return True
t=[]
output = filter(check_dump, input)
print(output)
True
import java.util.ArrayList;
public class C {
public static void main(String[] args) {
int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};
ArrayList<Integer> arr1 = new ArrayList<Integer>();
for(int i=0;i<arr.length-1;i++){
if(arr[i] == arr[i+1]){
arr[i] = 99999;
}
}
for(int i=0;i<arr.length;i++){
if(arr[i] != 99999){
arr1.add(arr[i]);
}
}
System.out.println(arr1);
}
}
これは単純な（N *（N-1）/ 2）ソリューションです。一定の追加スペースを使用し、元の順序を維持します。@Byjuによるソリューションに似ていますが、if(){}ブロックを使用しません。また、要素をそれ自体にコピーすることも回避します。
#include <stdio.h>
#include <stdlib.h>
int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])
size_t undup_it(int array[], size_t len)
{
size_t src,dst;
/* an array of size=1 cannot contain duplicate values */
if (len <2) return len;
/* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
size_t cur;
for (cur=0; cur < dst; cur++ ) {
if (array[cur] == array[src]) break;
}
if (cur != dst) continue; /* found a duplicate */
/* array[src] must be new: add it to the list of non-duplicates */
if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
dst++;
}
return dst; /* number of valid alements in new array */
}
void print_it(int array[], size_t len)
{
size_t idx;
for (idx=0; idx < len; idx++) {
printf("%c %d", (idx) ? ',' :'{' , array[idx] );
}
printf("}\n" );
}
int main(void) {
size_t cnt = COUNT;
printf("Before undup:" );
print_it(numbers, cnt);
cnt = undup_it(numbers,cnt);
printf("After undup:" );
print_it(numbers, cnt);
return 0;
}
これは、シングルパスで、入力リスト内の整数の数でO（N）時間で、一意の整数の数でO（N）ストレージで実行できます。
最初の項目に初期化された2つのポインタ「dst」と「src」を使用して、リストを前から後ろにウォークスルーします。「見た整数」の空のハッシュテーブルから始めます。srcの整数がハッシュに存在しない場合は、dstのスロットに書き込み、dstをインクリメントします。srcの整数をハッシュに追加してから、srcをインクリメントします。srcが入力リストの最後を通過するまで繰り返します。
binary tree the disregards duplicatesすべての要素を-に挿入しますO(nlog(n))。次に、トラバーサルを実行して、それらすべてを配列に抽出します- O(n)。注文の保存は必要ないと思います。
ハッシュにはブルームフィルターを使用します。これにより、メモリのオーバーヘッドが大幅に削減されます。
BinarySearchTreeO（n）の複雑さを持つを作成します。
JAVAでは、
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};
String value ="";
for(Integer i:arrayInteger)
{
if(!value.contains(Integer.toString(i))){
value +=Integer.toString(i)+",";
}
}
String[] arraySplitToString = value.split(",");
Integer[] arrayIntResult = new Integer[arraySplitToString.length];
for(int i = 0 ; i < arraySplitToString.length ; i++){
arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
}
出力：{1、2、3、4、6、7、8、9、10}
これが役立つことを願っています
まず、check[n]nが重複をなくしたい配列の要素の数である配列を作成し、（チェック配列の）すべての要素の値を1に設定する必要があります。forループを使用して配列をトラバースします。重複し、その名前がarrであると言い、forループに次のように記述します。
{
if (check[arr[i]] != 1) {
arr[i] = 0;
}
else {
check[arr[i]] = 0;
}
}
これで、すべての重複をゼロに設定します。したがって、あとはarr配列をトラバースして、ゼロに等しくないものをすべて出力するだけです。順序は維持され、線形時間（3 * n）がかかります。
n個の要素の配列が与えられた場合、時間O（nlogn）で配列からすべての重複を削除するアルゴリズムを記述します。
Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array
//input parameters :a[1:n], an array of n elements.
{
temp[1:n]; //an array of n elements.
temp[i]=a[i];for i=1 to n
temp[i].value=a[i]
temp[i].key=i
//based on 'value' sort the array temp.
//based on 'value' delete duplicate elements from temp.
//based on 'key' sort the array temp.//construct an array p using temp.
p[i]=temp[i]value
return p.
他の要素では、「キー」を使用して出力配列で維持されます。キーの長さがO（n）であり、キーと値の並べ替えにかかる時間はO（nlogn）であるとします。したがって、配列からすべての重複を削除するのにかかる時間はO（nlogn）です。
これは私が持っているものですが、それを修正するために昇順または降順で並べ替えることができる順序が間違っています。
#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];
for(x=0;x<n;x++){
printf("Enter a number for array[%d]: ",x);
scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
printf("%d\t",arr[x]);
}
int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");
for (int i = 0; i < n; i++)
{
// printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
for (int j = 0; j <n; j++)
{
if (i==j)
{
continue;
}
else if(arr[i]==arr[j]){
changedarr[j]=0;
}
else{
changedarr[i]=arr[i];
}
// printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
}
myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
if(changedarr[i]!=0){
count+=1;
printf("%d\t",changedarr[i]);
}
}
printf("\n");
}
整数が含まれているかどうかをすばやく判断できる優れたDataStructureがあれば、すばらしいでしょう。おそらくある種の木。
DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
if(elementsSeen.Contains(array[i])
elementsRemoved++;
else
array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;
ここに書かれている答えのいくつかは非常に些細なものであり（O（n ^ 2）またはO（NlogN）での並べ替えとトラバース）、Microsoftのインタビューで期待されていたものではないと思います。明らかに、O（n）を超える答えは、彼らが探していたものではありませんでした。更新では、ヘルパーデータ構造は存在しないはずであるため、ヘルパーデータ構造（ハッシュテーブル、ツリー、ビット配列など）を持つ回答は有効なソリューションではないはずです。
追加のメモリを割り当てることができる場合は、JeffBの答えがおそらくそれを行う最も簡単な方法です。このような質問には良い答えがありますが、MAXINTは配列のサイズによって制限される必要があります。（例：サイズ100の配列には、1から100までの任意の数を含めることができます。元の質問として重複を削除してください）
O（n）時間とO（1）メモリでのこれに対する答えは次のとおりです。
// FLAG ALL DUPS IN THE ORIGIN ARRAY
int maxNumInArray = findMaxNumInArray(arr);
int dup = findMinNumInArray(arr) - 1;
for (int i=0; i < arrLength; ++i) {
int seekIndex = arr[i] % (maxNumInArray+1);
if (arr[seekIndex] > maxNumInArray)
arr[i] = dup; // invalidate index
else
arr[seekIndex] = arr[seekIndex] + maxNumInArray;
}
// REMOVE EMPTY SPACES
int i = 0;
int j = arrLength(arr)-1;
while (i<j) {
while (arr[i] != dup)
++i;
while (arr[j] == dup)
--j;
swap(arr[i], arr[j]);
}
範囲がわからない場合、私の答えは役に立ちませんが、uはそれを試してみることができます。ああ、そしてこの特定のバリエーションは負の数では機能しませんが、それを修正するのに問題はありません。
C ++で簡単な解決策を知りたい人のために：
int* rmdup(int path[], int start, int end, int& newEnd) {
int ret[100];
newEnd = end;
int j = start;
for (int i = start; i < end; i++) {
if (path[i] == path[i+1]) {
newEnd--;
continue;
}
ret[j++] = path[i];
}
ret[j++] = path[end];
for(int i = start; i <= newEnd; i++)
path[i] = ret[i];
}
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};
Set set = new HashSet();
for(Integer i:arrayInteger)
set.add(i);
System.out.println(set);
変数x=arr[0]を取得し、残りの要素をトラバースしてxor演算を実行するだけです。要素が繰り返されると、xはゼロになります。
このようにして、要素が以前に繰り返されたことがわかります。これもo(n)、元の配列のすべての要素をスキャンするだけです。