C语言怎么实现数组去重
在 C 语言中,可以通过以下几种方法实现数组去重:
- 使用双重循环遍历数组,判断每个元素是否与后面的元素重复,如果重复则将后面的元素删除。这种方法的时间复杂度较高,为 O(n^2)。示例代码如下:
#include <stdio.h>
int removeDuplicates(int arr[], int n) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n;) {
if (arr[j] == arr[i]) {
for (k = j; k < n; k++) {
arr[k] = arr[k + 1];
}
n--;
} else {
j++;
}
}
}
return n;
}
int main() {
int arr[] = {1, 2, 3, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
n = removeDuplicates(arr, n);
printf("Array after removing duplicates: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
- 使用额外的数组或哈希表,遍历原始数组,将元素存储到新数组或哈希表中,如果元素已经存在,则跳过。这种方法的时间复杂度为 O(n)。示例代码如下:
#include <stdio.h>
int removeDuplicates(int arr[], int n) {
int temp[n];
int j = 0;
for (int i = 0; i < n; i++) {
int duplicate = 0;
for (int k = 0; k < j; k++) {
if (arr[i] == temp[k]) {
duplicate = 1;
break;
}
}
if (!duplicate) {
temp[j++] = arr[i];
}
}
for (int i = 0; i < j; i++) {
arr[i] = temp[i];
}
return j;
}
int main() {
int arr[] = {1, 2, 3, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
n = removeDuplicates(arr, n);
printf("Array after removing duplicates: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
- 对原始数组进行排序,然后遍历数组,删除相邻重复的元素。这种方法的时间复杂度取决于排序算法的复杂度,一般为 O(n log n)。示例代码如下:
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int removeDuplicates(int arr[], int n) {
qsort(arr, n, sizeof(int), compare);
int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != arr[i + 1]) {
arr[j++] = arr[i];
}
}
return j;
}
int main() {
int arr[] = {1, 2, 3, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
n = removeDuplicates(arr, n);
printf("Array after removing duplicates: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
以上三种方法都可以实现数组去重,具体选择哪种方法取决于实际需求和性能要求。