from:http://blog.csdn.net/MoreWindows/article/category/859207
數組A中，除了某一個數字x之外，其他數字都出現了三次，而x出現了一次。請給出最快的方法找到x。 這個題目非常有意思，在本人博客中有《位操作基礎篇之位操作全面總結》這篇文章介紹了使用位操作的異或來解決——數組中其他數字出現二次，而x出現一次，找出x。有《【白話經典算法系列之十二】數組中只出現1次的兩個數字(百度面試題)》這邊文章介紹了分組異或的方法來解決——數組中其他數字出現二次，而x和y出現一次，找出x和y。而這個題目則是其他數字出現3次，x出現一次。...
2013-10-21 11:49 閱讀(32100) 評論(34) 首先看看題目要求： 給定一個無序的整數數組，怎么找到第一個大于0，并且不在此數組的整數。比如[1,2,0]返回3，[3,4,-1,1]返回2，[1, 5, 3, 4, 2]返回6，[100, 3, 2, 1, 6,8, 5]返回4。要求使用O(1)空間和O(n)時間。 這道題目初看沒有太好的思路，但是借鑒下《白話經典算法系列之十一道有趣的GOOGLE面試題》這篇文章，我們不發現使用“基數排序”正好可以用來解決這道題目...
2013-10-15 10:17 閱讀(13580) 評論(11) 【白話經典算法系列之十五】“一步千里”之數組找數 有這樣一個數組A，大小為n，相鄰元素差的絕對值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。現在，給定A和目標整數t，請找到t在A中的位置。除了依次遍歷，還有更好的方法么？...
2013-09-02 12:57 閱讀(25918) 評論(39) 【白話經典算法系列之十三】隨機生成和為S的N個正整數——投影法 隨機生成和為S的N個正整數有很多種解法。下面講解一種比較高效且比較有趣味性的解法——投影法。 以生成和為20的4個數為例，可以先生成隨機生成0到20之間的三個數字再排序，假設得到了4，7，18。然后在X-Y數軸上畫出這三個數，如下圖：然后將這些數值投影到Y軸上，可得下圖：由圖很容易看出AB，BC，CD，DE這四段的長度...
2013-01-04 13:46 閱讀(15710) 評論(46) 微博http://weibo.com/MoreWindows已開通，歡迎關注。本系列文章地址：http://blog.csdn.net/MoreWindows/article/category/859207首先來看題目要求：在一個數組中除兩個數字只出現1次外，其它數字都出現了2次， 要求盡快找出這兩個數字。 考慮下這個題目的簡化版——數組中除一個數字只出現1次外，其它數字都成對出現，要求盡快...
2012-11-27 09:17 閱讀(35498) 評論(51) 微博http://weibo.com/MoreWindows已開通，歡迎關注。本系列文章地址：http://blog.csdn.net/MoreWindows/article/category/859207 上一篇《白話經典算法系列之十一道有趣的GOOGLE面試題》中對一道有趣的GOOGLE面試題進行了詳細的講解，使用了類似于基數排序的做法在O(N)的時間復雜度和O(1)的空間復雜度完成了題目的要...
2012-11-23 07:57 閱讀(24806) 評論(52) 微博http://weibo.com/MoreWindows已開通，歡迎關注。最近在微博上看到一道有趣的GOOGLE面試題，見下圖：文字版：一個大小為n的數組，里面的數都屬于范圍[0, n-1]，有不確定的重復元素，找到至少一個重復元素，要求O(1)空間和O(n)時間。 這個題目要求用O(n)的時間復雜度，這意味著只能遍歷數組一次。同時還要尋找重復元素，很容易想到建立哈希表來完成，遍歷數組...
2012-11-21 09:03 閱讀(47907) 評論(87) 首先來看看原題 微軟2010年筆試題在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序數對。一個排列中逆序的總數就稱為這個排列的逆序數。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序數對，因此整個數組的逆序數對個數為4，現在給定一數組，要求統計出該數組的逆序數對個數。 計算數列的逆序數對個數最簡單的方便就最從前向后依次統計每個數字與它后面...
2012-10-15 09:15 閱讀(30367) 評論(36) 在我的博客對冒泡排序，直接插入排序，直接選擇排序，希爾排序，歸并排序，快速排序和堆排序這七種常用的排序方法進行了詳細的講解，并做成了電子書以供大家下載。下載地址為：http://download.csdn.net/detail/morewindows/4443208。 有網友提議到這本《MoreWindows白話經典算法之七大排序》電子書講解細致用來平時學習是非常好的，但是頁數有22頁...
2012-09-10 10:08 閱讀(42997) 評論(26) 堆排序與快速排序，歸并排序一樣都是時間復雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先講解下什么是數據結構中的二叉堆。二叉堆的定義二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足二個特性：1．父結點的鍵值總是大于或等于（小于或等于）任何一個子節點的鍵值。2．每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。當父結點的鍵值總是大于或等于任何一個子節點的鍵值時為最大堆。當父...
2011-08-22 20:04 閱讀(338481) 評論(188) 快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被采用，再加上快速排序思想----分治法也確實實用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程序方面的考試如軟考，考研中也常常出現快速排序的身影。總的說來，要直接默寫出快速排序還是有一定難度的，因為本人就自己的理解對快速排序作了下白話解釋，希望對大家理解有幫助，達到快速排序，快...
2011-08-13 17:19 閱讀(418202) 評論(284) 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。首先考慮下如何將將二個有序數列合并。這個非常簡單，只要從比較二個數列的第一個數，誰小就先取誰，取了后就在對應數列中刪除這個數。然后再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。//將有序數組a[]和b[]合并到c[]中 void MemeryArra...
2011-08-11 11:01 閱讀(275147) 評論(154) 直接選擇排序和直接插入排序類似，都將數據分為有序區和無序區，所不同的是直接播放排序是將無序區的第一個元素直接插入到有序區以形成一個更大的有序區，而直接選擇排序是從無序區選一個最小的元素直接放到有序區的最后。 設數組為a[0…n-1]。 1. 初始時，數組全為無...
2011-08-09 11:15 閱讀(29055) 評論(38) 希爾排序的實質就是分組插入排序，該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。 該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增...
2011-08-08 11:41 閱讀(148913) 評論(82) 直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。 設數組為a[0…n-1]。 1. 初始時，a[0]自成1個有序區，無序區為a[1..n-1]。...
2011-08-06 19:27 閱讀(118661) 評論(81) 冒泡排序是非常容易理解和實現，，以從小到大排序舉例： 設數組長度為N。 1．比較相鄰的前后二個數據，如果前面數據大于后面的數據，就將二個數據交換。 2．這樣對數組的第0個數據到N-1個數據進行一次遍歷后，最大的一個數據就“沉”到數組第N-1個位置。 3．N=N-1，如果N...
2011-08-06 19:20 閱讀(166505) 評論(94)