質問は少し複雑です。ここでの問題は、重複を取り除き、配列の一意の要素を元のシーケンスで別の配列に保存することです。
例えば ：
入力が入力された場合bacadt
結果は : 入力が入力された正確な状態の bacdt になります。
そのため、元のシーケンスを失ったため、配列を並べ替えてからチェックすることはできませんでした。インデックスの配列を使用するようにアドバイスされましたが、その方法がわかりません。それで、それをするためのあなたのアドバイスは何ですか？
質問に答えたい人のために、具体的な情報を追加したいと思います。
char** finduni(char *words[100],int limit)
{
//
//Methods here
//
}
は私の機能です。重複を削除して別の配列に格納する必要がある配列は、words[100] です。したがって、プロセスはこれで行われます。最初に、単語のすべての要素を別の配列に取得してその配列をソートすることを考えましたが、いくつかのテストの後、それは機能しません。ソルバー向けのリマインダーです:)。
さて、これはcharタイプのバージョンです。スケーリングしないことに注意してください。
#include "stdio.h"
#include "string.h"
void removeDuplicates(unsigned char *string)
{
unsigned char allCharacters [256] = { 0 };
int lookAt;
int writeTo = 0;
for(lookAt = 0; lookAt < strlen(string); lookAt++)
{
if(allCharacters[ string[lookAt] ] == 0)
{
allCharacters[ string[lookAt] ] = 1; // mark it seen
string[writeTo++] = string[lookAt]; // copy it
}
}
string[writeTo] = '\0';
}
int main()
{
char word[] = "abbbcdefbbbghasdddaiouasdf";
removeDuplicates(word);
printf("Word is now [%s]\n", word);
return 0;
}
出力は次のとおりです。
Word is now [abcdefghsiou]
それはあなたが望むもののようなものですか？文字間にスペースがある場合はメソッドを変更できますが、タイプとしてint、float、doubleまたはを使用するとchar *、このメソッドはまったくスケーリングされません。
編集
投稿してから、あなたの説明を見ました。ここでは、の配列ですchar *。メソッドを更新します。
これが多すぎるコードでないことを願っています。この QuickSort アルゴリズムを採用し、基本的にインデックス メモリを追加しました。アルゴリズムは O(n log n) です。以下の 3 つのステップは加算的であり、そのうちの 2 つの最悪の場合の複雑さです。
originalIndices番目の要素は、並べ替えられた配列の i 番目の要素の元のインデックスを保持します。NULL、インデックス値を に設定しelementsます。これは可能な最大値です。NULL.コード：
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
void sortArrayAndSetCriteria(char **arr, int elements, int *originalIndices)
{
#define MAX_LEVELS 1000
char *piv;
int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R;
int idx, cidx;
for(idx = 0; idx < elements; idx++)
originalIndices[idx] = idx;
beg[0] = 0;
end[0] = elements;
while (i>=0)
{
L = beg[i];
R = end[i] - 1;
if (L<R)
{
piv = arr[L];
cidx = originalIndices[L];
if (i==MAX_LEVELS-1)
return;
while (L < R)
{
while (strcmp(arr[R], piv) >= 0 && L < R) R--;
if (L < R)
{
arr[L] = arr[R];
originalIndices[L++] = originalIndices[R];
}
while (strcmp(arr[L], piv) <= 0 && L < R) L++;
if (L < R)
{
arr[R] = arr[L];
originalIndices[R--] = originalIndices[L];
}
}
arr[L] = piv;
originalIndices[L] = cidx;
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
}
else
{
i--;
}
}
}
int removeDuplicatesFromBoth(char **arr, int elements, int *originalIndices)
{
// now remove duplicates
int i = 1, newLimit = 1;
char *curr = arr[0];
while (i < elements)
{
if(strcmp(curr, arr[i]) == 0)
{
arr[i] = NULL; // free this if it was malloc'd
originalIndices[i] = elements; // place it at the end
}
else
{
curr = arr[i];
newLimit++;
}
i++;
}
return newLimit;
}
void sortArrayBasedOnCriteria(char **arr, int elements, int *originalIndices)
{
#define MAX_LEVELS 1000
int piv;
int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R;
int idx;
char *cidx;
beg[0] = 0;
end[0] = elements;
while (i>=0)
{
L = beg[i];
R = end[i] - 1;
if (L<R)
{
piv = originalIndices[L];
cidx = arr[L];
if (i==MAX_LEVELS-1)
return;
while (L < R)
{
while (originalIndices[R] >= piv && L < R) R--;
if (L < R)
{
arr[L] = arr[R];
originalIndices[L++] = originalIndices[R];
}
while (originalIndices[L] <= piv && L < R) L++;
if (L < R)
{
arr[R] = arr[L];
originalIndices[R--] = originalIndices[L];
}
}
arr[L] = cidx;
originalIndices[L] = piv;
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
}
else
{
i--;
}
}
}
int removeDuplicateStrings(char *words[], int limit)
{
int *indices = (int *)malloc(limit * sizeof(int));
int newLimit;
sortArrayAndSetCriteria(words, limit, indices);
newLimit = removeDuplicatesFromBoth(words, limit, indices);
sortArrayBasedOnCriteria(words, limit, indices);
free(indices);
return newLimit;
}
int main()
{
char *words[] = { "abc", "def", "bad", "hello", "captain", "def", "abc", "goodbye" };
int newLimit = removeDuplicateStrings(words, 8);
int i = 0;
for(i = 0; i < newLimit; i++) printf(" Word @ %d = %s\n", i, words[i]);
return 0;
}
As Thomas suggested in a comment, if each element of the array is guaranteed to be from a limited set of values (such as a char) you can achieve this in O(n) time.
bool (or int if your compiler doesn't support bool) or however many different discrete values could possibly be in the array. Initialize all the values to false.bool array is false, add it to the output array and set the bool array value to true. Otherwise, do nothing.O(n)操作O(log n)操作最後に、O(n log n)操作
Cでは2番目の配列を作成できると思います。次に、この要素がまだ送信配列にない場合にのみ、元の配列から要素をコピーします。これにより、要素の順序も保持されます。
要素を 1 つずつ読み取ると、元の配列に挿入する前に要素を破棄できます。これにより、プロセスが高速化される可能性があります。
char型の場合のやり方は知っていますよね？文字列でも同じことができますが、ブール配列 (技術的には「セット」オブジェクトの実装) を使用する代わりに、文字列の線形配列で「セット」(またはブール配列) をシミュレートする必要があります。あなたはすでに遭遇しました。つまり、すでに見た文字列の配列があります。新しい文字列ごとに、それが「見られた」文字列の配列にあるかどうかを確認し、そうであれば無視し（一意ではありません）、配列にない場合は追加します見られた文字列の配列と出力の両方にそれを。少数の異なる文字列 (1000 未満) がある場合は、パフォーマンスの最適化を無視して、新しい各文字列を以前に見たすべてのものと単純に比較できます。
ただし、文字列の数が多い (数千) 場合は、少し最適化する必要があります。
1）すでに見た文字列の配列に新しい文字列を追加するたびに、挿入ソートアルゴリズムで配列をソートします。データがほぼソートされている場合、挿入ソートの方が高速になる傾向があるため、クイックソートは使用しないでください。
2) 文字列が配列内にあるかどうかを確認するときは、バイナリ検索を使用します。
異なる文字列の数が妥当な場合 (つまり、数十億の一意の文字列がない場合)、このアプローチは十分に高速です。