一个大小为N的数组，里面是N个整数，怎样去除重复的数

题目：一个大小为N的数组，里面是N个整数，怎样去除重复的数字；

要求时间复杂度为O(n)，空间复杂度为O(1).

需要除掉重复的整数的数组，注意这里我没有处理负数情况，其实负数情况只要先用0快排分一下组，然后各自用以下算法进行处理即可。 另外因为是整数，这里没考虑32位符号位，只考虑31位。

题目分析：从要求来看，如果一个数组是排好序的，除掉重复就很简单，因此就转换成了排序算法寻找，这种算法需要满足：线性时间，常量内存，原地置换。但纵观这么多算法，比较排序肯定不行，那么就只有基数排序，桶排序和计数排序，计数排序排除，因为计数排序无法原地置换，桶排序也需要辅助空间，所以最后考虑用 基数排序，基数排序依赖于位排序，而且要求位排序是稳定的， 且不能过多使用辅助空间，这里问题是如何选择位排序，因为位上只有0和1，因此有其特殊性，使用快排的分组就可以达到线性，但问题是这种算法虽然是线性，原地置换，但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考，发现，如果从高位开始排序，假设前K位是排好的，对K+1进行排序时，只针对前K位的相同的进行，前K位不相同，也不可能相等，第K+1位也不影响结果，而前K位相同的排序，就不怕快排的不稳定了，因为这个不稳定不会影响到最终结果。

C++代码实现如下：

#include<iostream>

using namespace std;

bool isbitof1(int num,int index);//判断num的index位是否为1,index从0开始

void partition_m(int data[],int start,int end,int index,bool (*cond)(int,int));//分割函数

void linear_sort(int data[],int n);//线性排序，基于基数排序，关键字为某位二进制位是0还是1，一共32位

int delete_repeated(int data[],int n);

int main()

{

    int N;//数组元素个数

    cin>>N;//用户输入

    int *data=new int[N];

    int i;

    for(i=;i<N;i++)

        cin>>data[i];//输入数组元素

    int len=delete_repeated(data,N);

    for(i=;i<len;i++)

        cout<<data[i]<<" ";

    cout<<endl;

    return ;

}

bool isbitof1(int num,int index)

{

    num=(num>>=index)&;//判断index位是零还是1

    if(num==)

        return true;

    else

        return false;

}

void partition_m(int data[],int start,int end,int index,bool(*cond)(int,int))

{

    if(data==NULL||start>end)

        return;

    int i=start-;

    int j=end+;

    while(true)

    {

        do

        {

            i++;

        }while(!cond(data[i],index)&&i<=end);

        do

        {

            j--;

        }while(cond(data[j],index)&&j>=start);

        if(i>j)

            break;

        int temp=data[i];

        data[i]=data[j];

        data[j]=temp;

    }

}

void linear_sort(int data[],int n)

{

    if(data==NULL||n<=)

        return;

    int indexofbit,i,processed_bit;

    //从高位到低位

    for(indexofbit=;indexofbit>=;indexofbit--)

    {

        int start=;

        int end=;

        int prev=(data[]>>(indexofbit+))&(0x7FFFFFFF);

        for(i=;i<n;i++)

        {

            processed_bit=(data[i]>>(indexofbit+))&(0x7FFFFFFF);

            if(processed_bit==prev)

                end=i;

            else

            {

                partition_m(data,start,end,indexofbit,isbitof1);

                prev=(data[i]>>(indexofbit+))&(0X7FFFFFFF);

                start=i;

                end=i;

            }

        }

        partition_m(data,start,end,indexofbit,isbitof1);

    }

}

int delete_repeated(int data[],int n)

{

    linear_sort(data,n);

    int i,j;

    i=;

    j=i+;

    while(j<n)

    {

        if(data[j]!=data[i])

        {

            i++;

            data[i]=data[j];

            j++;

        }

        else

        {

            j++;

        }

    }

    return i+;

}

转自：http://blog.csdn.net/jirongzi_cs2011/article/details/11626207

更多：http://blog.csdn.net/hawksoft/article/details/6867493

一个大小为N的数组，里面是N个整数，怎样去除重复的数的相关教程结束。