計數排序法(Counting Sort),只需線性時間就能完成的超快排序法 2017 年 10 月 21 日 Magic Len 研究分享、 Go、 Java、 Rust、 演算法、 JavaScript 計數排序(Counting Sort)演算法是不需進行比較的排序演算法,顧名思義,它會去數元素的數量來進行排序。這種排序法只需要線性時間和空間的複雜度就可以完成排序,比時間複雜度為O(nlogn)的演算法還快,而且作法也不會太難。雖然如此,計數排序法是並不算是常見的排序演算法,因為它只能用來排序已知數值範圍的序列(由於要直接對應序列的索引值,所以這組數值通常會是一組整數)。舉例來說,已知序列中的每... 繼續閱讀
[HackerRank]快速排序1─劃分(Quicksort 1 - Partition) 2017 年 10 月 18 日 Magic Len 程式解題、 Java 給定一個陣列ar和一個支點p,p=ar[0],並將陣列ar依據支點p劃分為left(左邊)、right(右邊)或是equal(相等)。left為小於支點p的所有元素,right為大於支點p的所有元素,equal為等於支點p的所有元素(包含支點p)。 繼續閱讀
[HackerRank]完整的計數排序(The Full Counting Sort) 2017 年 10 月 4 日 Magic Len 程式解題、 Java 使用計數排序法依據清單上每個項目的整數數值來排序清單,並且保留整數相同之項目的原始順序。排序後依序輸出原本輸入清單之後半段項目的字串內容,前半段的項目只要輸出減號「-」即可。 繼續閱讀
[HackerRank]權力遊戲I(Game of Thrones - I) 2017 年 10 月 3 日 Magic Len 程式解題、 Java 多斯拉其語正在計劃發動一個攻擊來竄取羅伯特國王的王位。羅伯特國王從烏鴉那得知了這場陰謀。並計劃鎖住敵人唯一能通過的那扇門。然而,要鎖住那扇門必須要有一個鑰匙,這個鑰匙是一個回文字串的變位詞。請幫助他判斷一個字串的變位詞是否為回文。 繼續閱讀
[HackerRank]愈大愈好(Bigger is Greater) 2017 年 10 月 2 日 Magic Len 程式解題、 Java 給定一個文字W,請重新排列W的字母使得它構成另一個文字S,且這個文字S的字典排序必須在文字W之後。由於可能會有很多種答案,請找出並輸出字典排序在最前面的那個文字。 繼續閱讀
[HackerRank]計數排序3(Counting Sort 3) 2017 年 10 月 1 日 Magic Len 程式解題、 Java 一個已排序的清單,用來作為排序依據的元素常常只是其他值的某個鍵值或是屬性。舉例來說,如果您正在根據檔案大小來排序檔案,檔案的大小必須跟它們所對應的檔案互相連結。您不能只單純地排序檔案大小,然後將其輸出,您會需要輸出跟這些檔案有關的必要資訊。如果您真的不需要其他資訊,您可以簡單的排序那些數值就好,這也可以讓計數排序變得更加容易。您只要已經計算過清單中數值出現的次數,就不用再去存取原本的清單。然而,當... 繼續閱讀
[HackerRank]計數排序2(Counting Sort 2) 2017 年 9 月 30 日 Magic Len 程式解題、 Java 一個已排序的清單,用來作為排序依據的元素常常只是其他值的某個鍵值或是屬性。舉例來說,如果您正在根據檔案大小來排序檔案,檔案的大小必須跟它們所對應的檔案互相連結。您不能只單純地排序檔案大小,然後將其輸出,您會需要輸出跟這些檔案有關的必要資訊。然而,如果您真的不需要其他資訊,您可以簡單的排序那些數值就好,這也可以讓計數排序變得更加容易。如果您已經計算過清單中數值出現的次數,那麼您就不用再去存取原本的清... 繼續閱讀
[HackerRank]演算法的執行時間(Running Time of Algorithms) 2017 年 9 月 29 日 Magic Len 程式解題、 Java 插入排序法在排序未排序過的龐大陣列時,會需要很多時間。為了瞭解究竟是什麼原因所造成的,我們需要分析一下執行時間。輸入一個未排序的陣列,請輸出使用插入排序法將這個陣列排列好的話,會需要移動幾次元素。 繼續閱讀
[HackerRank]正確性和循環不變性(Correctness and the Loop Invariant) 2017 年 9 月 28 日 Magic Len 程式解題、 Java 完成插入排序法,並將陣列排序後輸出。 繼續閱讀
[HackerRank]計數排序1(Counting Sort 1) 2017 年 9 月 27 日 Magic Len 程式解題、 Java 快速排序法的時間複雜度為O(nlog2n),還有什麼演算法可以排序更快呢?一般來說,大部分的演算法都需要進行「比較」,所以在最差的案例下最快也是需要nlog2n的執行時間。然而在某種類型的輸入條件下,使用「非比較」的演算法會更有效率,只需要線性時間就可以完成計算。給定一個整數陣列,請算出各數值出現的次數。 繼續閱讀