어레이에서 중복을 제거하고 다른 어레이에 저장
그래서 나는 다른 기존 배열에서 중복 된 값없이 배열을 만드는 임무를 받았습니다. 그래서 해냈지만 다른 더 좋은 방법이 있는지 알고 싶습니다.
입력 / 출력 예 :
Input: 10, 15, 10, 5, 1, 3
Output: 10, 15, 5, 1, 3
그래서 여기에 내 코드가 있습니다.
#include <stdio.h>
int main(void) {
const int MAX_ARRAY_SIZE = 5;
int m[MAX_ARRAY_SIZE], p[MAX_ARRAY_SIZE];
for(int i = 0; i < MAX_ARRAY_SIZE; i++) {
printf("Enter number: ");
scanf("%d",&m[i]);
}
int k = 0;
int dup = 0;
for(int i =0; i < MAX_ARRAY_SIZE; i++) {
for(int j = i +1; j <MAX_ARRAY_SIZE; j++) {
if(m[i] == m[j]) {
dup = 1;
}
}
if(dup != 1) {
p[k++] = m[i];
}
dup = 0;
}
printf("The new array without repeated values\n");
for(int i = 0; i < k; i++) {
printf("%d\n",p[i]);
}
return 0;
}
이것이 내가 그렇게하는 옳고 간단한 방법인지 확실하지 않습니다. 몇 가지 제안을 원합니다.
미리 감사드립니다. :)
답변
조기 종료
후
dup = 1;
당신은해야합니다 break. 나머지 루프를 실행할 필요가 없습니다.
부울
사용하고 <stdbool.h>, 만들고 bool dup = false, 나중에 할당하고 true, 쓰는 것을 고려하십시오 if (!dup).
복잡성
실질적으로 5 개 값의 배열은 계산 비용이 없습니다. 그러나 교수님이 복잡성 분석에 관심이 있다면 이에 대한 "적절한"솔루션은 의사 코드를 사용하여 해시 세트와 같은 것을 사용하여 선형 시간 (현재 2 차 시간이 아닌)으로 완료해야합니다.
Set *seen = make_set();
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
int m;
scanf(&m);
if (!contains(seen, m))
add(seen, m);
}
for (m in seen)
printf(m);
이 Q는 자체적으로 중복 제거가 필요합니다. 중복 제거 ... 그러나 이것이 내부 루프의 세 번째 버전이므로 새로운 시작을 활용합니다.
int j = i + 1;원래 for-expression-list에 압축 된 이 비 공격적인 할당 j은 마지막 i에 대해 초기화 하는 것 이상 을 수행합니다 m[j]. 불법 / 정의되지 않게 만듭니다 .
목표 (?)는 dup플래그 를 피하고 루프를 "정규화"하는 것입니다. 이 재배치가 그만한 가치가 있다고 생각합니다.
int j;
for (int i = 0; i < ARRAY_SIZE; i++) {
j = i;
do
if (++j == ARRAY_SIZE) { // already past end?
p[k++] = m[i]; // copy this one
break; // and finish
}
while (m[i] != m[j]); // if match, then just finish
}
이제 모든 것이 자연스러운 위치에 있습니다.
나는 do statement while (expr);구조를 설명하기 위해 중괄호없이 썼다 . 숨겨진 부분은 루프 증분 if (++j...입니다.
실제 (정렬 된) 구조 대신 새로운 고유 배열을 사용하여 중복을 검색 할 수 있습니다. 왜냐하면의 0이미 새로운 배열 I 무조건 우선 첫 번째 요소를 복사하고, 다음 두 번째 요소 루프를 시작한다.
int k = 1;
/* First is always unique */
printf("m[0] -> p[0]\n");
p[0] = m[0];
for (int i = 1; i < ARRAY_SIZE; i++)
for (int j = 0;; j++) {
if (j == k) {
printf("m[i=%d] -> p[k=%d]\n", i, k);
p[k++] = m[i];
break;
}
if (p[j] == m[i])
break;
}
그래도 이것은 if (p[j] == m[i])논리적으로 뒤에 if (j == k)있어야하므로 for 루프는 약간 자유 형식이어야합니다.
printf들 설명 :
Enter number: 6
Enter number: 6
Enter number: 0
Enter number: 0
Enter number: 8
m[0] -> p[0]
m[i=2] -> p[k=1]
m[i=4] -> p[k=2]
The array without repeated values
6
0
8
부작용 : 이제 순서가 유지됩니다.
검색과 삽입이 매우 밀접하게 연결되어 있기 때문에 이것은 약간 까다로운 것 같습니다. k지수는 정확하게 처리해야합니다. (다른 것들도)
성능 : 최대 k까지의 새 어레이를 사용하는 것이 원본의 나머지를 검색하는 OP보다 빠른지조차 모릅니다. 어떤 경우에는 적어도 같은 정도 인 것 같습니다.
문제는 새 배열이 정렬되지 않는다는 것입니다. 모든 삽입 후 순진하게 수행하면 정렬 유지 비용이 너무 많이 듭니다.
따라서 효율적으로 검색하려면 먼저 "확산"해야합니다. (무작위) 정수의 경우 모듈로 10은 10 개의 서로 다른 배열 또는 버킷을 만들 수 있습니다. 2D 사용 b[][](OP 대신 p[])
b[0] {100}
b[1] {1, 31, 20001}
b[2] {12, 32, 502}
b[3] {}
b[4] {94}
...
모든 (하위) 배열 ARRAY_SIZE은 최악의 경우 원본이 필요합니다 . 그러나 이제 dups를 검색하는 어레이는 평균 10 배 더 짧습니다.
따라서 대화 형 입력을 100 만 정수 배열 생성기로 변경하고 몇 가지 테스트를 수행 할 수 있습니다.
dup루프 플래그 때문에 모두 ;)