学习|C++冒泡排序小习题

Vaccae

发布于 2020-05-14 15:14:20

3960

发布于 2020-05-14 15:14:20

文章被收录于专栏：微卡智享

前言

最近也是自己在学习数据结构和算法，个人觉得学习最好的方法就是输出倒逼输入，所以这段时间文章可能也会以一些算法的习题为主吧，主要现在也没有什么存货文章了。

这篇主要是因为在五一长假中，同事的亲戚一个大学的考试题给了我，然后看了一下有点小意思，就把他做了，顺便分享一下。

题目

微卡智享

题目分析

乍一看这题还很长，但是仔细分析一下，主要就是两点：

#	题目要求
1	对字符串进行排序
2	遇到前缀相同的输出最长的那一个（包括相同的）

相对来说这个题还是比较简单的，在力扣里面应该也算是简单题目吧，下面我们看看解题思路。

解题思路

我们直接用Example中的2来列一下思路，如下面动画方式

使用冒泡排序把输入的字符串数组进行按字母顺序的排序。
因为是已经排序好的数组，我们就开始遍历数组，在新数组中不存在的就插入，然后每个字符串都与新数组中最后一个字符串进行对比，如果相同的就排除，如果不同的就插入到新数组中。
这样最后新的数组中就存在的不重复的而且已经排序好了数组，进行输出即可。

Tips

上面的解决方法中，开始先使用冒泡排序的时间复杂度为O(n2)，排好序后遍历原来的数组的时间复杂度为O(n)，对比新数组中的数据就可以不再需要遍历查找了，因为前面我们已经排过序，所以对比最后一次插入的数据的时间复杂度为O(1)。

代码实现

#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<vector>#include<algorithm>
using namespace std;
vector<char*> vtpre;vector<char*> vtnew;
bool checkchr(char*, char*);void dealvtsnew(char*);
int main(int argc, char** argv) {    int count; //输入的个数    cout << "输入基因序列数量" << endl;    scanf("%d", &count);
    char* chr;    for (int i = 0; i < count; ++i) {        char *chr=new char[100];        scanf("%s", chr);        vtpre.push_back(chr);    }    //排序数组    //使用冒泡排序重新做了排序    int n = vtpre.size() - 1;    for (int i = 0; i < n; ++i) {        for (int j = 0; j < n - i - 1; ++j) {            if (checkchr(vtpre[j], vtpre[j+1])) {                char* tmpchr = vtpre[j];                vtpre[j] = vtpre[j+1];                vtpre[j + 1] = tmpchr;            }        }    }
    //遍历数组进行处理    for (int j = 0; j < vtpre.size(); ++j) {        dealvtsnew(vtpre[j]);    }
    //输出结果    cout << endl;    cout << "结果" << endl;    for (int k = 0; k < vtnew.size(); ++k) {        cout << vtnew[k] << endl;    }
    return 0;}
//比较两个char*bool checkchr(char* chr1, char* chr2) {    //判断哪个长用于记录    int prelen = strlen(chr1);    int newlen = strlen(chr2);    int time = prelen > newlen ? newlen : prelen;    //进行字符串对比    for (int i = 0; i < time; ++i) {        //不相等直接插入新数组，然后跳出        if (chr1[i] < chr2[i]) {            return false;        }        else if (chr1[i] > chr2[i]) {            return true;        }    }        if (prelen < newlen) return true;    return false;}
//进行新的数组处理void dealvtsnew(char *pre){    if (vtnew.size() == 0) {        vtnew.push_back(pre);    }    else {        //取最后一个数组值        char* chr = vtnew.back();
        //进行字符串对比        for (int i = 0; i < strlen(pre); ++i) {            //不相等直接插入新数组，然后跳出            if (pre[i] != chr[i]) {                vtnew.push_back(pre);                return;            }        }    }}

实现效果