前言 昨晚搞了個acm題，當時沒考慮到內存限制，用了int數組，然後鏈表動態分配的方法，結果內存不夠無法ac，今天考慮了一下，用數組唯一性的原理就可以實現了。難點在於用char數組存儲數據，可以節約內存空間。 特殊的數 題目描述： 現在有n個數，其中有一些出現了一次，一些出現了兩次，一些出現了很多次。現在要求你找出那些只出現一次的數，並按升序輸出。 輸入： 本題有多組case。 每個case有兩行，第一行輸入一個n，表示有n個數，1<= n <= 1000000。 第二行有n個數字。每個數字的大小范圍[1, 1000000]。 輸出： 每次輸出有兩行。 第一行輸出一個整數，表示出現一次的數的個數。 第二行按升序輸出出現次數為一次的數字，兩個數字之間用空格隔開。 樣例輸入： 5 1 2 2 3 3 7 1 2 2 3 4 4 2 2 2 2 樣例輸出： 1 1 2 1 3 0 AC代碼 key唯一性 [cpp] #include <stdio.h> #include <stdlib.h> #include <string.h> #define max 1000001 int main() { int i, n, count, temp, j; char a[max]; while(scanf("%d", &n) != EOF) { memset(a, 0, sizeof(a)); for(i = count = 0; i < n; i ++) { scanf("%d", &temp); if(a[temp] == 0) { a[temp] += 1; count ++; }else if(a[temp] == 1) { a[temp] += 1; count --; }else { a[temp] += 1; } } printf("%d\n", count); if(count) { for(i = j = 0; i < max; i ++) { if(a[i] == 1) { if(j == count - 1) printf("%d\n", i); else printf("%d ",i); j ++; } } } } return 0; } 不考慮內存，可以用鏈表&&排序實現，感覺自己寫的不錯，也貼出來吧（這個沒ac，因為內存超了限制，但是重要在學習方法） [cpp] #include <stdio.h> #include <stdlib.h> #include <string.h> struct lnode { int data; struct lnode *next; }; int compare(const void *a, const void *b); void createlist(struct lnode *, int); void cleanlist(struct lnode *); int main() { int num[1000001]; int i, n, j, k; struct lnode *p; while(scanf("%d", &n) != EOF) { //初始化數據 memset(num, 0, sizeof(num)); struct lnode *head = malloc(sizeof(struct lnode)); head->data = 0; head->next = NULL; //接收輸入數據 for(i = 0; i < n; i ++) { scanf("%d", &num[i]); } //快速排序，調用系統qsort qsort(num, n, sizeof(num[0]), compare); for(i = j = 0; i < n; i ++) { if(num[i] != num[i + 1]) { createlist(head, num[i]); j ++; }else { for(k = i; k < n; k ++) { if(num[i] != num[k]) { break; } } i = k - 1; } } //打印輸出 printf("%d\n", j); for(i = 0, p = head->next; p && i < j; p = p->next, i ++) { if(i == j - 1) printf("%d\n", p->data); else printf("%d ", p->data); } //清理鏈表 cleanlist(head); } return 0; } int compare(const void *a, const void *b) { int sign; sign = (*(int *)a - *(int *)b) * -1; return sign; } void createlist(struct lnode *head, int data) { struct lnode *s = malloc(sizeof(struct lnode)); s->data = data; s->next = head->next; head->next = s; } void cleanlist(struct lnode *head) { struct lnode *p; for(p = head; p; p = head) { head = head->next; free(p); } }
