华为机试-整形数组合并（较难）

题目描述

将两个整型数组按照升序合并，并且过滤掉重复数组元素。
输出时相邻两数之间没有空格。
请注意本题有多组样例。

感觉解法比较多 STL直接用
set自动排序+去重
map自动排序，输出first
vector的sort排序，然后unique+erase去重，或者双指针自己写个去重

#include<iostream>
#include<set>
using namespace std;
int main(){
    int num1,num2;
    int temp;
    while(cin>>num1){
        set<int> myset;
        while(num1--){
            cin>>temp;
            myset.insert(temp);
        }
        cin>>num2;
        while(num2--){
            cin>>temp;
            myset.insert(temp);
        }
        for(auto i:myset)
            cout<<i;
        cout<<endl;
    }


}

自己实现排序和去重，就当复习快排和双指针去重吧

#include<iostream>
#include<vector>
#include<stdlib.h>  
#include<time.h> 

using namespace std;
void quicksort(vector<int>& temp,int left,int right){
    if(left>=right) return;
    int vip;
    srand(time(NULL));
    vip=rand()%(right-left+1)+left;
    swap(temp[left],temp[vip]);//注意left不要写成0
    int v=temp[left];
    int le=left,ge=right,i=left+1;
    while(i<=ge){//这里不能用for循环，有的不需要i++
        if(temp[i]<v){
            swap(temp[i],temp[le]);
            le++;i++;
        }
        else if(temp[i]>v){
            swap(temp[i],temp[ge]);
            ge--;
        }
        else
            i++;
    }
    quicksort(temp,left,le-1);
    quicksort(temp,ge+1,right);
}
int removerepeat(vector<int>& temp){
    if(temp.size()==1) return 0;
    int low=0,fast=1;//low左边和本身是严格符合已去重的
    while(fast<temp.size()){
        if(temp[fast]!=temp[low]){
            low++;
            swap(temp[fast++],temp[low]);
        }
        else
            fast++;
    }
    return low;

}

int main(){
    int num1,num2;
    int a;
    while(cin>>num1){
        vector<int> temp;
        while(num1--){
            cin>>a;
            temp.push_back(a);
        }
        cin>>num2;
        while(num2--){
            cin>>a;
            temp.push_back(a);
        }
        quicksort(temp,0,temp.size()-1);//排序完成
        int pos=removerepeat(temp);//双指针去重完成
        for(int i=0;i<=pos;i++){
            cout<<temp[i];
        }
        cout<<endl;
    }


}

另一种快排（不适合重复数字多的时候）

int vipvalue(vector<int>& temp,int left,int right){
    srand(time(NULL));
    int vip=rand()%(right-left+1)+left;
    swap(temp[vip],temp[left]);
    int lt=left,i=left+1;
    while(i<=right){
        if(temp[i]<temp[left]){
            lt++;
            swap(temp[lt],temp[i]);
        }
        i++;
    }
    swap(temp[left],temp[lt]);
    return lt;//此时lt是轴值本身，lt左边都小于它
}
void quicksort(vector<int>& temp,int left,int right){
    if(left>=right) return;
    int vip;
    vip=vipvalue(temp,left,right);
    quicksort(temp,left,vip-1);
    quicksort(temp,vip+1,right);
}