C++算法问题求助非常感谢非常感谢

写个function, 里面包含一组英文名字的array, 然后去掉重复的名字;剩下的名字都是按照先前输入进array的顺序进行排列的. 比如三个名字 Mike, Andy, Cat.

可以使用binary search, mergesort等; 不能使用STL图书馆.
跪求代码

c++

2个回答

stl library怎么被翻译成“STL图书馆”

这个最简单的:

int function(string * arr, int n)
{
int x = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] != arr[x]) arr[++x] = arr[i];
}
return x + 1;
}

caozhy
每个人都有一个梦才不会孤单的说话就有天堂 回复JonathanYan: 嗯,没注意,以为原始数据是有序的
6 个月之前 回复
JonathanYan
JonathanYan 回复贵阳老马马善福专门编写代码的老马就是我!: 你这个是不是只能处理重复名字是连续的情况,比如“Andy Cat Andy Cat”得结果就不对了
6 个月之前 回复
caozhy
每个人都有一个梦才不会孤单的说话就有天堂 回复weixin_45620260: 问题解决请点采纳
6 个月之前 回复
weixin_45620260
weixin_45620260 回复: 老马 哈哈哈
6 个月之前 回复
weixin_45620260
weixin_45620260 多谢了老妈! 刚开始学算法 还是用的C++ 所以还要补很多知识. 太感谢了!!!
6 个月之前 回复

先对字符串排序,然后排除重复的,再按初始下标排序。
用堆排序快点。

#include <iostream>
#include <string>

using namespace std;

typedef struct V{
    int index;
    string str;
} V;

bool compByStr(V a, V b){
    return a.str > b.str;
}

bool compByIndex(V a, V b){
    return a.index > b.index;
}

void swap(V &a, V &b){
    V temp = a;
    a = b;
    b = temp;
}

void upHeap(V* s, int size, int index, bool (*comp)(V a, V b)){
    int f = index / 2;
    while(index){
        if(comp(s[f], s[index]))
            swap(s[f], s[index]);
        else
            break;

        index = f;
        f = index / 2;
    }
}

void downHeap(V* s, int size, int index, bool (*comp)(V a, V b)){
    int l = index * 2 + 1;
    int r = index * 2 + 2;
    while(l < size){
        int toSwap = l;

        if(r<size && comp(s[l], s[r]))
            toSwap = r;

        if(comp(s[index], s[toSwap]))
            swap(s[index], s[toSwap]);
        else
            break;

        index = toSwap;
        l = index * 2 + 1;
        r = index * 2 + 2;
    }
}

void makeHeap(V* s, int size, bool (*comp)(V a, V b)){
    for(int i = size/2; i >= 0; i--){
        downHeap(s, size, i, comp);
    }
} 

void pushHeap(V* s, int size, V val, bool (*comp)(V a, V b)){
    upHeap(s, size, size, comp);
}

V popHeap(V* s, int size, bool (*comp)(V a, V b)){
    V temp = s[0];
    s[0] = s[size - 1];
    downHeap(s, size - 1, 0, comp);
    return temp;    
}


int main(){
    int n, size, size2 = 0;
    cin >> n;
    size = n;

    V *list = new V[n];
    V *list2 = new V[n];
    for(int i = 0; i < size; i++){
        cin >> list[i].str;
        list[i].index = i;
    }

    makeHeap(list, size, compByStr);

    while(size){
        V a = popHeap(list, size, compByStr);
        if(!size2 || list2[size2-1].str != a.str)
            list2[size2++] = a;
        size--;
    }

    makeHeap(list2, size2, compByIndex);

    while(size2){
        V a = popHeap(list2, size2, compByIndex);
        cout << a.str << endl;
        size2--;
    }

    delete[] list;
    delete[] list2;

    return 0;
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问