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