列表排序、去重

Catalogue

1. 1. 问题
2. 2. 回答

问题

请用自己的算法, 按升序合并如下两个 list, 并去除重复的元素:

list1 = [2, 3, 8, 4, 9, 5, 6]
list2 = [5, 6, 10, 17, 11, 2]

回答

1. @bob 用 C++ 写了一下

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int list1[] = {2,3,8,4,9,5,6};
    int list2[] = {5,6,10,17,11,2};
    int length1 = sizeof(list1) / sizeof(list1[1]);
    int length2 = sizeof(list2) / sizeof(list2[1]);

    sort(list1,list1+length1);
    sort(list2,list2+length2);

    int list[length1+length2],index=0,i=0,j=0;

    while(i<length1 || j<length2){
        if(list1[i]==list2[j]){
            list[index++]=list1[i++];
            j++;
        }else if(list1[i]>list2[j]){
            list[index++]=list2[j++];
        }else{
            list[index++] = list1[i++];
        }
    }

    while(i<length1){
        list[index++] = list1[i++];
    }
    while(j<length2){
        list[index++] = list2[j++];
    }

    for(int i=0;i<index;i++)
        cout<<list[i]<<" ";

    return 0;
}

2. @capwill2

   我也刚刚用 C++写的 40 行。

   我的思路是先全部排序好，最后做一次归并。复杂度为排序的复杂度，用的 stl 的 sort，O(nlogn)。其实可以直接考虑使用 set 容器，直接去重并排序。