帮我写一个C语言数组去重算法
时间: 2023-06-28 07:07:03 浏览: 74
当需要对一个数组进行去重时,可以使用如下的C语言代码:
```c
#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 2, 4, 5, 3, 6, 1};
int len = sizeof(arr) / sizeof(int);
int i, j, k;
for (i = 0; i < len; ++i) {
for (j = i + 1; j < len;) {
if (arr[j] == arr[i]) {
for (k = j; k < len; ++k) {
arr[k] = arr[k + 1];
}
--len;
} else {
++j;
}
}
}
for (i = 0; i < len; ++i) {
printf("%d ", arr[i]);
}
return 0;
}
```
该算法的思路是:遍历数组中的每个元素,然后再遍历该元素后面的所有元素,如果后面的元素与当前元素相同,则将其删除(即将后面的元素向前移动一位),直到后面没有相同的元素为止。
相关问题
C语言数组去重算法,最好的算法
C语言数组去重的算法有多种,以下是其中一种常见的算法:
1. 先将数组排序,然后遍历数组,将重复的元素删除。
2. 用一个新数组来存储不重复的元素,遍历原数组,如果元素在新数组中不存在,则将该元素加入新数组中。
下面是第二种算法的示例代码:
```c
#include <stdio.h>
int main()
{
int arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int new_arr[n], k = 0;
// 遍历数组,将不重复的元素存入新数组中
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < k; j++) {
if (arr[i] == new_arr[j]) {
break;
}
}
if (j == k) {
new_arr[k++] = arr[i];
}
}
// 输出新数组
for (int i = 0; i < k; i++) {
printf("%d ", new_arr[i]);
}
printf("\n");
return 0;
}
```
这个算法的时间复杂度为 O(n^2),如果使用哈希表等数据结构,可以将时间复杂度降至 O(n),但需要额外的空间开销。
stl容器c语言实现数组去重
在C语言中,可以通过使用STL容器来实现数组去重的功能。STL(Standard Template Library)是C++标准库的一部分,提供了一系列的容器和算法,方便开发者进行数据结构和算法的实现。
在C语言中,可以使用哈希表来实现数组去重。哈希表是一种以键值对形式存储数据的数据结构,通过将元素的值映射到一个唯一的索引位置来实现快速的查找和插入操作。
以下是使用哈希表实现数组去重的步骤:
1. 创建一个空的哈希表。
2. 遍历原始数组中的每个元素。
3. 对于每个元素,检查哈希表中是否已经存在该元素。
- 如果存在,则说明该元素已经出现过,不需要再次插入到结果数组中。
- 如果不存在,则将该元素插入到哈希表中,并将该元素添加到结果数组中。
4. 返回结果数组,即为去重后的数组。
下面是一个示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define HASH_SIZE 100
typedef struct Node {
int value;
struct Node* next;
} Node;
typedef struct HashTable {
Node* buckets[HASH_SIZE];
} HashTable;
void initHashTable(HashTable* hashTable) {
for (int i = 0; i < HASH_SIZE; i++) {
hashTable->buckets[i] = NULL;
}
}
int hash(int value) {
return value % HASH_SIZE;
}
bool contains(HashTable* hashTable, int value) {
int index = hash(value);
Node* node = hashTable->buckets[index];
while (node != NULL) {
if (node->value == value) {
return true;
}
node = node->next;
}
return false;
}
void insert(HashTable* hashTable, int value) {
int index = hash(value);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->next = hashTable->buckets[index];
hashTable->buckets[index] = newNode;
}
void removeDuplicates(int* arr, int size) {
HashTable hashTable;
initHashTable(&hashTable);
int result[size];
int resultSize = 0;
for (int i = 0; i < size; i++) {
if (!contains(&hashTable, arr[i])) {
insert(&hashTable, arr[i]);
result[resultSize++] = arr[i];
}
}
printf("去重后的数组:");
for (int i = 0; i < resultSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 2, 3, 5};
int size = sizeof(arr) / sizeof(arr);
removeDuplicates(arr, size);
return 0;
}
```
运行以上代码,输出结果为:去重后的数组:1 2 3 4 5