algorithm - ソートされたリスト内のアイテムのインデックスを見つける

Question

生成されたリストがあります：

1. 003
2. 012
3. 021
4. 030
5. 102
6. 111
7. 120
8. 201
9. 210
10. 300

(数字は 0 から 3 までで、それらの合計は 3 です)

それらを数えずに組み合わせがどの場所にあるかを見つける方法は?? 元。201 -> index=8 よろしくお願いします。

Answer 1

そうです、私が行ってきた質問の下のコメントは、検索を実行せずに、現在の値からインデックスに直接移動したいと考えていることを前提としています。つまり、エントリの数字を調べて、それを 1 から始まる数字に変換します。

この回答は方向性があり不完全であることに注意してください。問題にアプローチする方法を示しているだけです。

あなたの例を見ると、各エントリを 3 桁(z_i, y_i, x_i)で構成されるものとして扱うと、次のシーケンスが得られます。

1. 003; z=0、y=0、x=3
2. 012; z=0、y=1、x=2
3. 021; z=0、y=2、x=1
4. 030; z=0、y=3、x=0
5. 102; z=1、y=0、x=2
6. 111; z=1、y=1、x=1
7. 120; z=1、y=2、x=0
8. 201; z=2、y=0、x=1
9. 210; z=2、y=1、x=0
10. 300; z=3、y=0、x=0

最大桁数がk (=3) の場合、次のようになります。

x_i = 3, 2, 1, 0, 2, 1, 0, 1, 0, 0 = k, k-1, ..., 0, k-1, ... 0, ......, 0

y_i = 0, 1, 2, 3, 0, 1, 2, 0, 1, 0 = 0, 1, ..., k, 0, ..., k-1, ......, 0

z_i = 0, 0, 0, 0, 1, 1, 1, 2, 2, 3 = k+1 x 0, k x 1, ......., 1 x k

ご覧のとおり、y_iの数字は順番に繰り返し上昇し、各補完の最後にz_iをノックアップします。

桁数が多い場合、パターンはより複雑になりますが、同様のパターンに従います。

k=4の場合:

1. 0004
2. 0013
3. 0022
4. 0031
5. 0040
6. 0103
7. 0112
8. 0121
9. 0130
10. 0202
11. 0211
12. 0220
13. 0301
14. 0310
15. 0400
16. 1003
17. 1012
18. 1021
19. 1030
20. 1102
21. 1111
22. 1120
23. 1201
24. 1210
25. 1300
26. 2002年
27. 2011年
28. 2020年
29. 2101
30. 2110
31. 2200
32. 3001
33. 3010
34. 3100
35. 4000

エントリの合計は、最初または最後の列から見ることができk+1ますk=4。の場合k=3、それは単に の三角形ですk+1。

うまくいきませんでしたが、そのパターンは、桁数が増えるにつれて連続した合計を示している可能性があります。

まだパターンがあります：

k=3:

k=4:

k=5:

または、一般に、長さkのシーケンス内のエントリの総数:

この知識は、最初の桁のスカラーを見つけるのに役立ち、残りの問題は実質的に のサブ問題ですk-1。現時点で私を倒す...

Answer 2

を使用しCollections.binarySearchます。

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch(java.util.List , T) を確認してください