ソートの問題

42212 ワード
テキストリンク

cppでソート


他の言語と同様にstd::アルゴリズムにはsortという非常に強力なソート関数が内蔵されていますが、それだけでは解決できない問題は本当に多いです.

counting sort


質問する
他のソート問題に比べて、正解率は特に低い...通常はカウントを外すとタイムアウトするためかもしれません.
原理は別の記事で紹介されていますが、ここではコードと解答方法だけを書くと、
#include <iostream>

#define MAX_NUM 10001
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    int arr[n], ans_arr[n];
    int counter = 0;
    int count[MAX_NUM] = {0};

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        arr[i] = val;
    }
    
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i <= MAX_NUM + 1; i++) {
        count[i] += count[i-1];
    }

    for (int i = 0; i < n; i++) {
        ans_arr[count[arr[i]]- 1] = arr[i];
        count[arr[i]]--;
    }
    
    for (int i = 0; i < n; i++) {
        cout << ans_arr[i] << "\n";
    }
}
その名の通りカウントsortを実現することで解くことができる.
しかし、このカウントsortの真の価値は次の問題にある.

統計学


リンク
問題だけを見れば、正解率が30%を下回る理由だが、これは最低価格のためだ.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
#define MAX_NUM = 8001

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    int avg, mid, most, range;
    cin >> n;

    vector<int> vec;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }

    int arr[n], ans_arr[n];
    int counter = 0;
    int count[MAX_NUM] = {0};

    for (int i = 0; i < n; i++) {
        arr[i] = vec[i];
    }
    
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i <= MAX_NUM + 1; i++) {
        count[i] += count[i-1];
    }

    for (int i = 0; i < n; i++) {
        ans_arr[count[arr[i]]- 1] = arr[i];
        count[arr[i]]--;
    }


    sort(vec.begin(), vec.end());

    avg = static_cast<int>(accumulate(vec.begin(), vec.end(), 0) / n);
    mid = vec[static_cast<int> (n/2)];
    most = 최빈값 구하기 
    range = vec.back() - vec.front();
    
    cout << avg <<"\n";
    cout << mid <<"\n";
    cout << most <<"\n";
    cout << range <<"\n";
}
驚くべきことに、最高価格を求める内蔵関数はありません.Rかmatlabにあるはずですがcppにはありませんしたがって、この最も頻繁な値を得るにはcounting sortを使用する必要があります.counting sortは、各要素の出現回数を統計することによって、最大値のidxが最も頻繁な値になる方法である.
しかしこの問題では,トラップには正数だけでなく負数もある.したがって、受信カウントsortの配列*2+1を用意し、0がarr.size()/2の位置にあることを確認し、各数値を計算する必要があります.

ダブルソート


条件Aと条件Bがあり、条件に従って並べ替えられるという問題がある.
例えば、x座標の小さい順序は、同じであればy座標の順序がこれらの問題である.

11650


リンク
上記の座標の問題です.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class point {
    public:
    int x;
    int y;

    point(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

bool coord_comp(point &a, point &b) {
    if (a.x < b.x) {
        return true;
    } else if (a.x == b.x) {
        if (a.y < b.y) {
            return true;
        } else return false;
    } else return false;
}

int main() {
    int n;
    cin >> n;
    int x, y = 0;
    vector<point> vec;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        vec.push_back(point(x, y));
    }

    sort(vec.begin(), vec.end(), coord_comp);
    for (int i = 0; i < n; i++) {
        cout << vec[i].x << " " << vec[i].y << "\n";
    }
}
これらの問題は,classや構造体として値を解くだけでよい.
point x,yを受け入れるx,y classを用いて値を受け入れベクトルに格納する.
次にbool compare関数を作成し、sortリファレンスのソートルールを作成します.
bool coord_comp(point &a, point &b) {
    if (a.x < b.x) {
        return true;
    } else if (a.x == b.x) {
        if (a.y < b.y) {
            return true;
        } else return false;
    } else return false;
}
比較するaとbにa.x2つの数の値が同じである場合、yは同じ方法で比較される.それ以外は、交換が起こらないようにfalseをすべて返却します.
それ以外にも、年齢ソート、文字列長ソートなど様々な問題があり、一つさえ分かれば残りの問題も同様に解決できる.

あっしゅくざひょう


これは問題を理解するのが少し難しい問題です.最初は最大の座標からだと思っていたが、座標は1、それから2と、このように解けた.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main() {
    int n, temp;
    cin >> n;
    vector<int> vec;
    vector<int> sorted;
    vector<int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
        sorted.push_back(val);
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i++) {
        if (temp != vec[i]) {
            temp = vec[i];
            vec2.push_back(vec[i]);
        }
    }
    vec.clear();

    for (int i = 0; i < n; i++) { 
        int dis;
        dis = find(vec2.begin(),vec2.end(), sorted[i]) - vec2.begin();
        vec.push_back(dis);
    }

    for (int elem : vec) {
        cout << elem << " ";
    }
}
このクレイジーなfor文コードを作成しました.もちろん、erase uniqueを使用すると、このコードもより速くなります.
どうせそうではない.

あっしゅくざひょう


リンク
問題は、配列内の要素elemより小さい要素の個数が座標の圧縮値になることです.
したがって、24〜104〜9であれば23031である.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vec;
    vector<int> sorted;
    vector<int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
        sorted.push_back(val);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for(int i = 0; i < n; i++) {
        int ans = lower_bound(vec.begin(), vec.end(), sorted[i]) - vec.begin();
        cout << ans << " ";
    }
}
この質問の答え順は以下の通りです.

  • 2つのベクトルの入力値を受け入れます.(1つは元の保存用、もう1つはソート用)

  • ベクトルをソートします.

  • 重複する値はすべて消去されます.

  • オリジナルの周囲をループし、整列したvectorからidxを取得します.
    • ここで重複値を除去するために使用される関数はeraseとuniqueです.

    unique


    ユニーク関数は、指定したvecotr範囲内の重複値をすべてゴミ値に送信し、ゴミ値の開始位置を返します.

    erase


    eraseは範囲内の値をクリアする役割を果たします.
    したがって,両者を組み合わせて使用すれば,ごみ価格の起点から終点まですべて削除できる.
    また、idxをインポートするプロセスはfor文でも実現できますが、内蔵関数low boundを使用することもできます.

    lower_bound


    この関数は、範囲内のベクトル値をsrcのバックエンド値と比較する役割を果たし、srcに対応するelemがある場合は最小idxを使用します.
    このようなプロセスにより、上記4段階を達成することができる.
    create-react-appとCodeSandboxで手軽にReactアプリの開発準備
    ロック解除