GEEKアルゴリズムの道——配列の重み付け

配列が重複要素を除去する問題は一般的に最も基本的で,あまり難しくなく,ほとんどの場合STLアルゴリズムや容器の性質を直接使えば済む.テーマを見てみましょう.
タイトル1
並べ替えられた配列を入力し、重複要素を除去し、新しい配列の長さを出力します.要件:連続したメモリで操作し、別の配列に追加のメモリ領域を割り当てないでください.挙栗:入力[1,1,2]、出力2.
ぶんせき
コンテナを追加で作成できる場合は、setを使用してvectorの値をsetに渡してから戻すことができます.set自体が重複しない性質を持っているからです.以下ではsetを用いたコードを先に示しますが、もちろん本テーマには向いていません.追加作成はできません.STLアルゴリズムuniqueも使用できます.STLアルゴリズムを用いなければ,自己書き込みサイクルで判断操作を行うことが考えられる.
コード#コード#
setバージョン(本題以外の答え)

//Remove Duplicates from Sorted Array
//Date:2016-04-05
//Author:Sin_Geek
//     O(n)，     O(n)

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    vector<int> a{1, 1, 2, 2, 3};
    set<int> b(a.cbegin(), a.cend());
    a.assign(b.cbegin(), b.cend());

    cout << a.size() <<endl;

    return 0;
}

Uniqueバージョン

//Remove Duplicates from Sorted Array
//Date:2016-04-05
//Author:Sin_Geek
//     O(n)，     O(1)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> a{1, 1, 2, 2, 3};

    cout << distance(a.begin(), unique(a.begin(), a.end())) << endl;

    return 0;
}

ループ判定

//Remove Duplicates from Sorted Array
//Date:2016-04-05
//Author:Sin_Geek
//     O(n)，     O(1)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> a{1, 1, 2, 2, 3};

    if (a.empty())
    {
       cout << 0 << endl;
       return 0;
    }


    int index = 0;
    for (int i = 1; i < a.size(); ++i)
    {
        if (a[index] != a[i])
            a[++index] = a[i];
    }

    cout << index + 1 << endl;

    return 0;
}