数组去重
对于默认排序的数组进行去重操作。
使用的方法可以形象地理解为 新旧表法。
下标 i 对应新表,j 对应旧表。初始化后,i 始终小于 j,因此 i 指向的存储空间始终有效,j 则顺序遍历旧表,新表与旧表在某种程度上不干扰,准确来说是已去重的数据和未处理的数据之间不存在交集,充分利用了当前的空间。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int uniq(int* arr, int arrSize);
int main()
{
int i, j;
int arrSize = 6;
int * arr = NULL;
arr = (int*)malloc(6*sizeof(int));
memset(arr,0,6*sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr[2] = 2;
arr[3] = 3;
arr[4] = 4;
arr[5] = 4;
for(i=0;i<arrSize;i++) {
printf("[%d]: %d\n",i,arr[i]);
} printf("----------\n");
arrSize = uniq(arr, arrSize);
for(i=0;i<arrSize;i++) {
printf("[%d]: %d\n",i,arr[i]);
} printf("----------\n");
return 0;
}
int uniq(int* arr, int arrSize) {
if(0==arrSize || 1==arrSize) return arrSize;
int i,j;
i = 0;
j = 1;
while(j<arrSize) {
if(arr[i]==arr[j]) {
j++;
} else {
arr[++i] = arr[j++];
}
}
return i+1;
}