23

式では

2 × *3年* 5年

x、yおよびは、z負でない整数値 (>=0) を取ることができます。

したがって、関数は一連の数値を生成します1,2,3,4,5,6,8,9,10,12,15,16....

  • 私はブルートフォースソリューションを持っています。
  • 基本的には、1 から始まるループを反復し、各反復で、現在の数値係数が 2、3、または 5 のセットのみからのものかどうかを確認します。

私が持ちたいのは、エレガントなアルゴリズムです。

これはインタビューの質問です。

4

9 に答える 9

32

これは、キー2 x 3 y 5 zでソートされたトリプレット(x、y、z)を格納する優先キューを使用して解決できます。

  1. キュー内のトリプレット(0, 0, 0)のみから開始します。

  2. 最小のキーを持つトリプレット(x、y、z)をキューから削除します。

  3. 3 つのトリプレット(x+1, y, z)、(x, y+1, z)および(x, y, z+1)をキューに挿入します。既に存在するものを挿入しないようにしてください。

  4. k 個のトリプレットを削除するまで、手順 2 から繰り返します。最後に削除されたものがあなたの答えです。

実際には、これはこの有向非巡回グラフのソートされた走査になります。(ここに示されている最初の 3 つのレベル、実際のグラフはもちろん無限大です)。

無限グラフ

于 2011-08-27T15:09:56.290 に答える
15

このページには膨大な数のプログラミング言語によるソリューションがリストされています。いつものように、Haskell バージョンは特にコンパクトで簡単です。

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y = x : xs `merge` (y:ys)
            | x > y = y : (x:xs) `merge` ys
            | otherwise = x : xs `merge` ys

更新Will Ness が指摘したように、既製の関数があり、それにData.List.Orderedは私よりも優れた選択肢がありますmerge(また、より適切な名前も付けられています)。

import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming
于 2011-08-27T15:39:55.463 に答える
11

私が考えることができる最も簡単な解決策：

    int[] factors = {2, 3, 5};
    int[] elements = new int[k];
    elements[0] = 1;
    int[] nextIndex = new int[factors.length];
    int[] nextFrom = new int[factors.length];
    for (int j = 0; j < factors.length; j++) {
        nextFrom[j] = factors[j];
    }
    for (int i = 1; i < k; i++) {
        int nextNumber = Integer.MAX_VALUE;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] < nextNumber) {
                nextNumber = nextFrom[j];
            }
        }
        elements[i] = nextNumber;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] == nextNumber) {
                nextIndex[j]++;
                nextFrom[j] = elements[nextIndex[j]] * factors[j];
            }
        }
    }
    System.out.println(Arrays.toString(elements));

これにより、そのセットの最初のk要素が O(k) 空間と時間で昇順に生成されます。

重複を排除するために、それを提供するすべてのnextNumberものから消費する必要があることに注意してください(結局、2*3 = 3*2)。 j

編集: アルゴリズムは、nm によって投稿された haskell と同じアプローチを使用します

于 2011-08-27T15:58:27.003 に答える
6

これは、アルゴリズムの知識以上のものをテストすることであり、どのように考え、問題を解決し、チームで働くかを含めます。

開始する前に、問題の適切な仕様を用意しておくことが重要です。説明されているように、不明な点には次のようなものがあります。

  • Kに境界はありますか？
  • 既知のアルゴリズムが必要ですか、それともアドホックのブルートフォースは問題ありませんか?
  • メモリ使用量と計算時間? （たぶん、どちらかが重要です）
  • 計算にかかる時間と開発にかかる時間はどれくらいですか?
  • 結果をキャッシュする必要がありますか?

これらの質問の一部またはすべてについてインタビュアーに尋ねることは、少なくとも、尋ねられた質問に答えることができることと同じくらい重要かもしれません. もちろん、この方法で自分を窮地に追い込むこともできます。

于 2011-08-27T15:10:27.820 に答える
2

この問題は、K 番目に小さい数を見つけることに変換できるため、

 f(x,y,z) = x log(2) + y log(3) + z log(5),

アルゴリズムは次のようになります

  1. f(x,y,z) = f(0,0,0) で始まる

  2. 現在の最小数 f(i,j,k) = v が与えられた場合、f(x,y,z) が v に最も近く、v を超えるような (x,y,z) を見つける必要があります。

    log(2)<log(3)<2log(2)<log(5)

    言うことが出来る

    0<=i-2<=x<=i+2, 0<=j-1<=y<=j+1 & 0<=k-1<=z<=k+1 such that f(x,y,z) > v

したがって、これは各ステップで最小の 45 個の値を見つけるためのものであり、O(K) アルゴリズムだと言えます。もちろん、(x,y,z)!=(i,j,k) などの条件をさらに課すことで、45 という数を減らすことができます。

于 2011-08-27T17:09:18.540 に答える
1

この種の問題には非常に洗練された解決策があります。アルゴリズムとコーディングは簡単です。時間計算量はO（n）です

私はどこかで同様の問題を見ました。問題は、2 ^ x.3^yの形式の番号を昇順で生成することでした。

だからここに行きます。

int kthsmallest(int k){

    int two = 0, three = 0, five = 0;
    int A[k];
    A[0] = 1;
    for (int i=1; i<k; i++){
        int min = (A[two] * 2 <= A[three] * 3)? A[two] * 2: A[three] * 3;
        min = (min <= A[five] * 5)? min: A[five] * 5;
        A[i] = min;
        if (min == A[two] * 2)
            two++;
        if (min == A[three] * 3)
            three++;
        if (min == A[five] * 5)
            five++;
    }
    return A[k-1];
}

アルゴリズムは基本的に-x、y、zに対して3つのポインターを保持します。コードでは、2、3、5を使用しました。すべての反復で、どれが小さいか（2 ^ x、3 ^ y、または5 ^ z）を確認します。その番号をi番目のインデックスに入れ、対応するx、y、またはzの値をインクリメントします。最小値が複数ある場合は、両方のポインターをインクリメントします。

于 2012-04-20T07:14:21.863 に答える
1

これらは、SRFI-41で例として使用したハミング数です。これは私がそこで使用したコードでした：

(define hamming
  (stream-cons 1
    (stream-unique =
      (stream-merge <
        (stream-map (lsec * 2) hamming)
        (stream-map (lsec * 3) hamming)
        (stream-map (lsec * 5) hamming)))))
于 2011-08-28T00:41:31.483 に答える
-1

x = y = z = 0 から始めます。各反復で 3 つの n を計算します。

nx = 2^(x+1)*3^y*5^z
ny = 2^x*3^(y+1)*5^z
nz = 2^x*3^y*5^(z+1)

3 つの中で最小の n を見つけます。

n = min(nx, ny, nz).

x、y、または z のいずれかを増やします。

If n == nx -> x = x + 1
If n == ny -> y = y + 1
If n == nz -> z = z + 1

K 回目の繰り返しの後に停止し、n を返します。

于 2011-08-27T15:09:53.603 に答える