回答編集履歴
5
修正
answer
CHANGED
|
@@ -40,7 +40,7 @@
|
|
|
40
40
|
|
|
41
41
|
発展的な方法
|
|
42
42
|
---
|
|
43
|
-
安定基数ソート。
|
|
43
|
+
安定~~基数ソート~~バケットソート。
|
|
44
44
|
```Python
|
|
45
45
|
import collections
|
|
46
46
|
|
4
追記
answer
CHANGED
|
@@ -36,4 +36,27 @@
|
|
|
36
36
|
```
|
|
37
37
|
{4: [4, 0], 6: [2, -1], 2: [2, -2]}
|
|
38
38
|
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
39
|
-
```
|
|
39
|
+
```
|
|
40
|
+
|
|
41
|
+
発展的な方法
|
|
42
|
+
---
|
|
43
|
+
安定基数ソート。
|
|
44
|
+
```Python
|
|
45
|
+
import collections
|
|
46
|
+
|
|
47
|
+
|
|
48
|
+
class OrderedCounter(collections.Counter, collections.OrderedDict):
|
|
49
|
+
pass
|
|
50
|
+
|
|
51
|
+
src = [4, 6, 2, 2, 6, 4, 4, 4]
|
|
52
|
+
counter = OrderedCounter(src)
|
|
53
|
+
|
|
54
|
+
dst = [
|
|
55
|
+
key
|
|
56
|
+
for key, num in counter.most_common()
|
|
57
|
+
for _ in range(num)
|
|
58
|
+
]
|
|
59
|
+
print(dst)
|
|
60
|
+
```
|
|
61
|
+
|
|
62
|
+
**参考：** [python - Creating an Ordered Counter - Stack Overflow](https://stackoverflow.com/questions/35446015/creating-an-ordered-counter)
|
3
修正
answer
CHANGED
|
@@ -36,31 +36,4 @@
|
|
|
36
36
|
```
|
|
37
37
|
{4: [4, 0], 6: [2, -1], 2: [2, -2]}
|
|
38
38
|
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
39
|
-
```
|
|
39
|
+
```
|
|
40
|
-
|
|
41
|
-
おまけ：惜しい方法
|
|
42
|
-
---
|
|
43
|
-
collections.Counterを使うと、簡潔で高速に実装できます。
|
|
44
|
-
```Python
|
|
45
|
-
import collections
|
|
46
|
-
|
|
47
|
-
src = [4, 6, 2, 2, 6, 4, 4, 4]
|
|
48
|
-
|
|
49
|
-
dst = list(collections.Counter(src).elements())
|
|
50
|
-
print(dst)
|
|
51
|
-
```
|
|
52
|
-
|
|
53
|
-
**実行結果** [Wandbox](https://wandbox.org/permlink/wnNA3HaTPZQXusl7)
|
|
54
|
-
```
|
|
55
|
-
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
56
|
-
```
|
|
57
|
-
|
|
58
|
-
基数ソートなので、組み込みソートに勝ち目は有りません。
|
|
59
|
-
ただし、なぜ惜しいと書いているかと言うと...
|
|
60
|
-
> **elements()**
|
|
61
|
-
それぞれの要素を、そのカウント分の回数だけ繰り返すイテレータを返します。要素は任意の順序で返されます。
|
|
62
|
-
|
|
63
|
-
引用元： [collections --- コンテナデータ型 — Python 3.7.4 ドキュメント](https://docs.python.org/ja/3/library/collections.html#collections.Counter.elements)
|
|
64
|
-
|
|
65
|
-
順序が保証されないからなんですね。
|
|
66
|
-
Counterとcollections.OrderedDictを継承させたクラスを使えば上手く行くのかな。
|
2
追記
answer
CHANGED
|
@@ -13,7 +13,7 @@
|
|
|
13
13
|
```
|
|
14
14
|
|
|
15
15
|
ただしlist.indexもlist.countも線型の計算量を要するので、
|
|
16
|
-
本来なら前以て評価用のデータを生成しておく
|
|
16
|
+
本来なら前以て評価用のデータを生成しておくのが好ましいです。
|
|
17
17
|
|
|
18
18
|
例えば、こんなふうに。
|
|
19
19
|
```Python
|
|
@@ -36,4 +36,31 @@
|
|
|
36
36
|
```
|
|
37
37
|
{4: [4, 0], 6: [2, -1], 2: [2, -2]}
|
|
38
38
|
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
39
|
-
```
|
|
39
|
+
```
|
|
40
|
+
|
|
41
|
+
おまけ：惜しい方法
|
|
42
|
+
---
|
|
43
|
+
collections.Counterを使うと、簡潔で高速に実装できます。
|
|
44
|
+
```Python
|
|
45
|
+
import collections
|
|
46
|
+
|
|
47
|
+
src = [4, 6, 2, 2, 6, 4, 4, 4]
|
|
48
|
+
|
|
49
|
+
dst = list(collections.Counter(src).elements())
|
|
50
|
+
print(dst)
|
|
51
|
+
```
|
|
52
|
+
|
|
53
|
+
**実行結果** [Wandbox](https://wandbox.org/permlink/wnNA3HaTPZQXusl7)
|
|
54
|
+
```
|
|
55
|
+
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
56
|
+
```
|
|
57
|
+
|
|
58
|
+
基数ソートなので、組み込みソートに勝ち目は有りません。
|
|
59
|
+
ただし、なぜ惜しいと書いているかと言うと...
|
|
60
|
+
> **elements()**
|
|
61
|
+
それぞれの要素を、そのカウント分の回数だけ繰り返すイテレータを返します。要素は任意の順序で返されます。
|
|
62
|
+
|
|
63
|
+
引用元： [collections --- コンテナデータ型 — Python 3.7.4 ドキュメント](https://docs.python.org/ja/3/library/collections.html#collections.Counter.elements)
|
|
64
|
+
|
|
65
|
+
順序が保証されないからなんですね。
|
|
66
|
+
Counterとcollections.OrderedDictを継承させたクラスを使えば上手く行くのかな。
|
1
追記
answer
CHANGED
|
@@ -13,4 +13,27 @@
|
|
|
13
13
|
```
|
|
14
14
|
|
|
15
15
|
ただしlist.indexもlist.countも線型の計算量を要するので、
|
|
16
|
-
本来なら前以て評価用のデータを生成しておくべきです。
|
|
16
|
+
本来なら前以て評価用のデータを生成しておくべきです。
|
|
17
|
+
|
|
18
|
+
例えば、こんなふうに。
|
|
19
|
+
```Python
|
|
20
|
+
key = {}
|
|
21
|
+
src = [4, 6, 2, 2, 6, 4, 4, 4]
|
|
22
|
+
|
|
23
|
+
for i, e in enumerate(src):
|
|
24
|
+
if e in key:
|
|
25
|
+
key[e][0] += 1
|
|
26
|
+
else:
|
|
27
|
+
key[e] = [1, -i]
|
|
28
|
+
|
|
29
|
+
print(key)
|
|
30
|
+
|
|
31
|
+
dst = sorted(src, key=key.get, reverse=True)
|
|
32
|
+
print(dst)
|
|
33
|
+
```
|
|
34
|
+
|
|
35
|
+
**実行結果** [Wandbox](https://wandbox.org/permlink/lSI09DlTbc0IHHD7)
|
|
36
|
+
```
|
|
37
|
+
{4: [4, 0], 6: [2, -1], 2: [2, -2]}
|
|
38
|
+
[4, 4, 4, 4, 6, 6, 2, 2]
|
|
39
|
+
```
|