インタビューの質問ごとに、「テストで全体的なスコアに基づいて10億人の学生のリストをどのように並べ替えるのですか? 1Bとマークの範囲は10-100です。 どのようなソートアルゴリズムも行いますが、効率的なアルゴリズムは何ですか?10億人の学生のリストを並べ替える
2
A
答えて
6
入力にはcounting sortを単に実行します。この場合は、範囲が制限されているため、O(n)
です。また、すべての生徒を出力する方法がΩ(n)であるため、最も効率的です。
利用可能なスコア(例えば、90の得点がある場合、生徒を90回ループする、スコア100の生徒を初めて出力する場合など)についてルーピングすることによって出力することができます。
このタスクはbucket sortで実行できます。しかし、まず入力をループして、各スコアに関連する生徒数を見つけ、その後、生徒数を考慮して各スコアのバケットを作成し、バケツを埋めて、バケットの配列を作成する必要があることに注意してください。現在のアイテム数を各バケットに保存する追加のパラメータ。
O(n)余分なスペースでO(n)、O(n)余分なスペースでO(n)ですが、2番目の方法は2*n
であるため、最初は90*n
です。
0
カウントソートを使用します。あなたが最大値とこの問題で満足されるいくつかの他のパラメータを知っているのは良いことです。
0
私はいくつかの種類の分割と征服アルゴリズム(マージソートやクイックソートやバケットソートなど)を使用し、このアイデアを使用して複数のバケット間でソートを分割します。 問題は、すべてのデータを結合して大きな配列に戻す必要がある場合に発生しますが、サブ配列が既にソートされているため、O(n)しかかかりません。
O(k)時間を取る2つのループとO(n)を取る1つのループがあり、合計時間はO(n + k)です。これは、kがnより小さい場合に有効です。例えば。スコアで1,000,000,000人をソートするとします。 n = 1000000000、k = 100-10、したがって時間= O(n)。
関連する問題
- 1. 生徒のリストを並べ替える
- 2. 並べ替えメソッドを持つ人物の並べ替え
- 3. 配列内の学生テストのスコアを並べ替える
- 4. 自分のコースの学生数でユーザーを並べ替える
- 5. リストのリストを並べ替える
- 6. Groovyのリストのリストを並べ替え
- 7. 並べ替えの生成
- 8. リストのスローを並べ替えるKeyNotFoundException
- 9. 教師IDに基づいて学生リストを並べ替えます
- 10. パンダ並べ替えリストstr.split()
- 11. 辞書学的に並べ替え
- 12. 長さで並べ替える前にリストをアルファベット順に並べ替える?
- 13. 2sxc従業員アプリケーションビジュアルクエリで並べ替えのリストを並べ替え
- 14. アルファベット順の並べ替えられていないリストを並べ替え
- 15. リストのサブセットをハイバネートで並べ替え
- 16. 選択並べ替え並べ替え
- 17. 並べ替えで並べ替え
- 18. Clojureのリストの並べ替え
- 19. Pythonのリストの並べ替え
- 20. リスト内のサブリストの並べ替え
- 21. N個のリストの並べ替え
- 22. リストをソート順に並べ替える
- 23. リストを並べ替えるSencha Touch
- 24. Pythonリストを並べ替える
- 25. リストを並べ替える - ピジョンソニック
- 26. C++の選択並べ替えなし並べ替え並べ替えなし
- 27. 並べ替えの方法配列インデックスで並べ替えられたリスト
- 28. リストを並べ替えると「void」エラーが発生する
- 29. Collections並べ替えて両方のArrayListを並べ替える
- 30. Facebook API -/taggable_friendsエンドポイントの並べ替えを並べ替える
2次基準として名前でマークするか、マークのみでソートしますか? – Gaim