質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

3回答

15499閲覧

C++中央値

megane_gr

総合スコア10

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

2クリップ

投稿2015/09/05 07:47

C++で中央値を求めるやり方がわかりません。
前に計算で求めるやり方を習ったのですが忘れてしまって…
if文でたらたら書くのはできるのですが。
かっこよく短い式で求めたいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yuba

2015/09/05 08:55

値の集合はどのように与えられる想定ですか? 配列やvector? それとも、変数a, b, c, d, eのような形?
guest

回答3

0

C++標準ライブラリで提供されるnth_elementアルゴリズムが使えます。

cpp

1#include <algorithm> 2#include <vector> 3#include <iostream> 4 5template <typename T> 6T median(std::vector<T>& c) 7{ 8 size_t n = c.size() / 2; 9 std::nth_element(c.begin(), c.begin() + n, c.end()); 10 return c[n]; 11} 12 13int main() 14{ 15 std::vector<int> a = {8,2,4,1,9,6,7,3,5}; 16 std::cout << median(a) << std::endl; // 5 17}

投稿2015/09/06 12:38

yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

anniepin

2017/01/27 11:47

nth_elementは「先頭に、順不同でN個の最高品質な要素を集める」なので、 その後、前半部分に対してmin_elementを使う必要がありそうです。
anniepin

2017/01/30 09:36

解説追記いただきありがとうございました。 cpprefjpサイトを見ましたが、min_elementについて誤った理解をしていました。 勉強になりました。
guest

0

ソートする関数を利用することは必須のように思えます.
しかし,ソートしてから中央値を求めるやり方より高速に求めることは可能です.

例えばO(n2)の選択ソートを自作したとき,途中までソートを完了させれば中央値はわかります.
全部を選択ソートでソートしてから中央値を求めるより,約1/4の時間で終わらせることができます.

またO(nlogn)のクイックソートを自作したとき,ピボットより大きいグループと小さいグループのどちらかはソート不要になります.
例えば{3, 1, 4, 6, 2, 7, 5}という元データを考えます.
ピボットを先頭の3にしたとき,{1, 2}, {3}, {4, 6, 7, 5}という風に分割できます.
この時,ピボットの3より小さいグループの要素数は2,等しいグループの要素数は1,大きいグループの要素数は4です.
となると中央値は大きいグループの中に入っていることがわかります.
というより大きいグループの1番小さい要素が中央値だということがわかります.
となるとピボットより小さいグループ内のソートは不要になります.
明らかに骨の折れるプログラミングですが,所要時間はかなり減るはずです.

もしこのような高速な求め方を実装している人がすでにいるとしたら,それを使うべきではありませんか?
私のアイディアよりももっと速いやり方を先人たちは開発しています.
英文ですが,最後の方にコードが有りますので,拝借するのが良いと思います.
Fast median search: an ANSI C implementation
先人は偉大です.

投稿2015/09/06 12:18

編集2015/09/06 12:26
KenTerada

総合スコア751

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

「if文でたらたら」というのがよく分からないのですが、基本的にはデータ列をソートして平均値付近から実測値を取得する処理ですし、ここの緑のチェックが付いている回答のように書くのが妥当です。

これ以上短く書く理由がある場合は、それを書かないと求める回答を得られないように思うのですが…

投稿2015/09/05 08:13

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問