有序向量去重算法

男娘i 2023-06-30 09:18 28阅读 0赞

### 文章目录 ###

*   *   *  场景
         *  算法实现
         *  运行实例

### 场景 ###

*  有序向量去重，理论上的最优解是O(n)

### 算法实现 ###

*  `算法复杂度 O(n) ,`

// 有序向量的唯一算法, 返回删除的元素个数
    int sortVectorUnique(vector<RANGE> &ages) {
        int old_size = ages.size();
        int left_index = 0, right_index = 0; // 相邻各异向量的秩
        while (++right_index < ages.size()) {
    
            // 相邻不同的数值迁移到左值的下一个位置
            if (ages[left_index] != ages[right_index]) {
                ages[++left_index] = ages[right_index];
            }
        }
    
        ages.resize(++left_index);
        // TODO 缩容
        return old_size - ages.size();
    }

### 运行实例 ###

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    typedef int RANGE;
    typedef int T;
    #define AGE_MIN 15
    #define AGE_MAX 25
    #define AGE_VECTOR_SIZE 15
    #define STATUS_ERROR -1
    
    // 返回 15 --45之间的年龄
    RANGE getRandAge() {
        return AGE_MIN + rand() % (AGE_MAX - AGE_MIN);
    };
    
    // 获取无序的向量
    vector<RANGE> getAgesVector() {
        vector<RANGE> ages;
        RANGE age_rand;
        for (int i = 0; i < AGE_VECTOR_SIZE; ++i) {
            age_rand = getRandAge();
            ages.push_back(age_rand);
            cout << age_rand << " ";
        }
        cout << "完成对向量ages的赋值" << endl;
        return ages;
    };
    
    // 无须向量查找 [lo, hi)
    int find(vector<RANGE> ages, RANGE lo, RANGE hi, T e) {
        if (hi > ages.size() || ages.size() < lo) {
            return STATUS_ERROR;
        }
    
        while (hi-- > lo) {
    
            if (ages[hi] == e) {
                cout << "下标=" << hi << "e=" << e << endl;
                return hi;
            }
        }
    
        return -1;
    };
    
    // 无需向量删除特定的秩 [lo,hi), 删除删除的大小 -1 表示异常
    int remove(vector<RANGE> &ages, RANGE lo, RANGE hi) {
        if (hi > ages.size() || ages.size() < lo) {
            return STATUS_ERROR;
        }
        if (hi < lo) {
            return STATUS_ERROR;
        }
    
        // 不需要删除
        if (hi == lo) {
            return 0;
        }
    
        RANGE old_size = ages.size();
    
        while (hi < ages.size()) {
            ages[lo++] = ages[hi++];
        }
        ages.resize(lo);
        return old_size - ages.size();
    }
    
    // 打印向量
    void showAges(vector<RANGE> ages) {
        for (int i = 0; i < ages.size(); ++i) {
            cout << " ages[" << i << "]=" << ages[i] << endl;
        }
        cout << "结束" << endl;
    }
    
    
    // 有序向量的唯一算法, 返回删除的元素个数
    int sortVectorUnique(vector<RANGE> &ages) {
        int old_size = ages.size();
        int left_index = 0, right_index = 0;
        while (++right_index < ages.size()) {
    
            // 相邻不同的数值迁移到左值的下一个位置
            if (ages[left_index] != ages[right_index]) {
                ages[++left_index] = ages[right_index];
            }
        }
    
        ages.resize(++left_index);
        // TODO 缩容
        return old_size - ages.size();
    }
    
    int main() {
        vector<RANGE> ages = {16, 17, 18, 19, 20, 20, 20, 21, 31};
        showAges(ages);
        int remove_size = sortVectorUnique(ages);
        showAges(ages);
        return 0;
    }