A是一个长度为N的整形数组，其中可能包含重复的元素，例如A={1,2,2,3,2,1,3,2}，删除数组中相同的元素后得到{1,2,3}， a) 如果数组没有排序，写一个C语言函数，输入参数为数组首地址和长度，删除其中重复的元素，返回删除后的数组的长度。 b) 上述函数的时间复杂度为多少，以删除前的数组长度N表示。 c) 如果数组A已经排好序，设计并写出一个C语言函数完成a)中的工作，要求时间复杂度是O(N) 。
#include<iostream>using namespace std;// a) 删除任意数组中相同的元素int delete_same_all(int a[], int n){ int i, j, len=n; for(i=0; i<len; ++i) for(j=i+1; j<len; ) if(a[i] == a[j]) a[j]=a[--len]; else ++j; return len;}// c)删除排序后的数组中相同的元素int delete_sort_same_all(int a[], int n){ int i, k=1; for(i=1; i<n; ++i) { if(a[i-1] != a[i]) { if(i != k) a[k] = a[i]; ++k; } } return k;}//打印数组void show(int *arr, int n){ int i=0; for(;i<n;i++) cout<<arr[i]<<" "; cout<<endl;}int main(){ int A[] = {1,2,2,3,2,1,3,2}; int n, len; n = sizeof(A)/sizeof(A[0]); len = delete_same_all(A, n); show(A, len); int B[] = {1,2,2,2,3,3,3,10,12,77,77,77}; n = sizeof(B)/sizeof(B[0]); len = delete_sort_same_all(B, n); show(B, len); return 0;}新闻热点
疑难解答
