分類  >  Web前端 >

回答: web前端筆試一道面試題目新解

tags:    時間:2013-12-10 19:36:01
答覆: web前端筆試一道面試題目新解
針對該問題,有兩種解法,無非就是時間和空間的權衡,在實際應用中根據具體情況而定,具體代碼就不寫了,分析如下,感興趣的歡迎PK。

第一種解法,犧牲時間換取空間,具體做法是:
1,首先對字元串進行排序,這一步的時間複雜度是固定的。可以有多種排序演算法選擇。
2,掃描排序后字元串,並且統計遇到的每個字元的數量。方法為:如果下一個字元和當前字元不一致,則當前統計到的數據就是該字元在字元串中出現的次數,此時拿該數據與之前出現過的最大的數據進行比較。
3,掃面結束之後即可以得到出現次數最多的字元,以及出現的次數。
在此過程中空間複雜度為:3,排序時候的空間複雜度為1,掃描階段需要記錄當前字元,當前字元出現的次數,以及曾經出現的最多字元的出現次數。


第二種解法,犧牲空間換取時間,具體做法是:
1,不排序,直接掃描字元串,每遇到一個之前沒遇到的字元就把它記下來,並設置其出現的次數為1,如果之前出現,則將該字元的出現次數加1.
2,在每掃描一個字元,並且得到該字元出現的次數時,就與最大的一個次數比較,得到新的最大的次數和字元。
3,掃描結束之後也就得到了結果

這個過程中只需要遍歷字元串一次,時間複雜度是線性的,空間複雜度為(字元串中出現的不同的字元串的次數+1)*2.

--有疑問請繼續跟帖。

1 樓 liuzhiqiangruc 2010-12-11  
該問題為:

尋找一個字元串中出現最多的字元,以及出現了多少次

推薦閱讀文章

Bookmark the permalink ,來源:互聯網