Определить третий квартиль из набора целых чисел в C++?

Question

Я читаю Ускоренный C++. На данный момент я нахожусь в конце главы 3 и вот упражнение, которое я пытаюсь сделать:

"Напишите программу для вычисления и вывода квартилей набора целых чисел".

Я нашел первый и второй квартили, но понятия не имею, как найти третий. Вот мой код:

 #include <algorithm>
 #include <iostream>
 #include <vector>
 using namespace std;

 int main(){
    cout<<"Enter numbers:";
    int x;
    vector<int>integers;
    while(cin>>x)
        integers.push_back(x);

    typedef vector<int>::size_type vec_sz;
    vec_sz size = integers.size();
    sort(integers.begin(), integers.end());
    vec_sz mid = size/2;
    vec_sz q1 = mid/2;
    double median;
    median = size % 2 == 0 ? ((double)integers[mid] + (double)integers[mid-1]) / 2
: integers[mid];
    double quartOne = ((double)integers[q1] + (double)integers[q1-1])/2; 
    cout<<"The First Quartile is: "<<quartOne<<endl;
    cout<<"The Second Quartile is: "<<median<<endl;
    return 0;
}

Answer 1

Один из способов - отсортировать коллекцию и затем взять 3 разделительных элемента:

vector<int> v = ...;
sort(v.begin(), v.end());
int q12 = v[v.size()*1/4];
int q23 = v[v.size()*2/4];
int q34 = v[v.size()*3/4];

Это O(nlogn) в количестве элементов данных.

Другим способом было бы выполнить двоичный поиск данных для трех подразделений отдельно. т. е. предложить начальное значение q12, проверить, правильно ли оно, сделав передачу данных, если оно неверно, скорректировать его вверх или вниз наполовину, и повторить. Сделайте так же для q23 и q34.

Технически это O(n), потому что 32-битное int имеет фиксированный диапазон и может быть подвергнуто двоичному поиску за 32 прохода макс.

Answer 2

Это решение реализует второй метод, описанный в Википедии для вычисления квартилей. Он обеспечивает правильные значения как для векторов с нечетной, так и четной длиной.

#include <vector>
#include <tuple>
#include <iostream>
using namespace std;

double median(vector<double>::const_iterator begin,
              vector<double>::const_iterator end) {
    int len = end - begin;
    auto it = begin + len / 2;
    double m = *it;
    if ((len % 2) == 0) m = (m + *(--it)) / 2;
    return m;
}

tuple<double, double, double> quartiles(const vector<double>& v) {
    auto it_second_half = v.cbegin() + v.size() / 2;
    auto it_first_half = it_second_half;
    if ((v.size() % 2) == 0) --it_first_half;

    double q1 = median(v.begin(), it_first_half);
    double q2 = median(v.begin(), v.end());
    double q3 = median(it_second_half, v.end());
    return make_tuple(q1, q2, q3);
}

int main() {
    vector<double> v = {2, 2, 3, 4, 4, 5, 5, 10};
    auto q = quartiles(v);
    cout << get<0>(q) << "," << get<1>(q) << "," << get<2>(q) << endl;
    return 0;
}

Он предназначен для действительных чисел, но его легко адаптировать к целочисленным значениям (просто округлить значения до ближайшего целого числа).