程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> lintcode: ugly number

lintcode: ugly number

編輯:C++入門知識

lintcode: ugly number


問題描述

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 …

問題分析

這個題,有多種方法求解,常見的是有輔助數據結構,比如priority_queue,或是常說的最大最小堆也可。

解法一:時間復雜度O(k log k),空間復雜度O(k)

使用priority_queue模擬最小堆: priority_queue, greater >. 從中取出最小的 ugly number , 然後該 ugly number 分別乘以3, 5, 7 然後又放進 priority_queue中 如果上述過程中,將乘以3,5,7之後的數直接放入 priority_queue 將可能導致重復放入的問題,比如:當取出 9, 然後放入27, 45, 63,。後面當取出 21 時,放入 63, 105, 147,這裡就重復放入 63 了。因此需要用個 unordered_set 來 mark 哪些元素已經放入過了。

時間復雜度分析:共 k 個元素,每次取出一個元素時,都需要對堆進行操作,時間復雜度為 O(k),因此時間復雜度為 O(k log k).

解法二:時間復雜度 O(k),空間復雜度O(k)

使用 primes 數組來記錄前 k 個ugly_number。在生成 primes 數組時,新增入的元素,肯定是該 primes 數組中前面某些元素乘以3,或是乘以5,或是乘以7的結果,且是最小的。依據此思想,可以構建如下的代碼
class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    long long kthPrimeNumber(int k) {
        // write your code here
        vector primes(k+1);
        primes[0] = 1;
        int i3 = 0, i5 = 0, i7 = 0;
        for (int i = 1; i <= k; i++) {
            long long nextPrime = min( min(primes[i3]*3, primes[i5]*5), primes[i7]*7 );
            if (nextPrime == primes[i3]*3) i3++;
            if (nextPrime == primes[i5]*5) i5++;
            if (nextPrime == primes[i7]*7) i7++;
            primes[i] = nextPrime;
        }
        return primes[k];
    }

};

復雜度分析:現在只需要進行 k 次操作,每次操作耗時是 O(1),因此總的時間復雜度是 O(k),而總的時間復雜度是 O(k)。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved