Re: [問題] 關於眾數問題

看板C_and_CPP (C/C++)作者yauhh (喲)時間15年前 (2010/10/21 17:09)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串2/3 (看更多)

※ 引述《applea123 (小刀)》之銘言： : 最近在寫眾數問題 : 主要是考慮到眾數>2時 : ex:1 1 1 1 1 2 2 2 2 3 3 3 4 4 : 眾數有1 2 : 次數4 : 我自己是有寫出來但是想問問大家有沒更快的"想法" : 我的步驟: : 1.排序並丟入a[] : 2.用一個陣列b[]紀錄各數出現次數並使用另一個對應陣列c[]來記錄此數字 : 3.陣列b排列並且c一起做交換 : 4.判斷b[] if(b[i]=b[i+1]) : 5.印出b[] 與c[] 我的作法沒很快,很基本: 一直線掃描,看過的數字把頻次加一,沒看過的數字填入表中. (見 find函數) struct Freq { int n; int times; struct Freq *next; }; struct Freq* find(int list[], int len) { struct Freq* lookup(struct Freq *list, int n); int i; struct Freq *result = NULL; for (i=0; i<len; i++) { struct Freq *p, *q; p = lookup(result, list[i]); if (p == NULL) { q = (struct Freq*)malloc(sizeof(struct Freq)); q->n = list[i]; q->times = 1; q->next = result; result = q; } else { p->times++; } } return result; } struct Freq* lookup(struct Freq *list, int n) { struct Freq *p = list; while (p != NULL) { if (p->n == n) return p; p = p->next; } return p; } 如此可以很簡單找到數頻表: int main() { struct Freq* find(int list[], int len); void layout(struct Freq *list); int list[14] = {1,1,3,1,4,2,4,2,2,3,3,1,2,1}; struct Freq *flist = find(list, 14); layout(flist); system("pause"); return 0; } void layout(struct Freq *list) { struct Freq *p = list; while (p!= NULL) { printf("%2d%2d\n", p->n, p->times); p = p->next; } } 輸出為: 2 4 4 2 3 3 1 5 Press any key to continue . . . 要不要排序隨便你. 如果只要找眾數群: int main() { struct Freq* find(int list[], int len); void layout(struct Freq *list, int d); int list[14] = {1,1,3,1,4,2,4,2,2,3,3,1,2,1}; struct Freq *flist = find(list, 14); layout(flist, 2); system("pause"); return 0; } void layout(struct Freq *list, int d) { struct Freq *p = list; int max = 0; printf("Modes: "); while (p!= NULL) { if (p->times > d) printf("%2d", p->n); if (p->times > max) max = p->times; p = p->next; } printf("\n"); printf("Maximal frequency: %d\n", max); } 輸出為: Modes: 2 3 1 Maximal frequency: 5 Press any key to continue . . . 完成. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.21.94.199