腾讯面试题（除掉N个整数中重复数）解题（线性时间，原地置换排序算法）(已修正）

题目：一个大小为N的数组，里面是N个整数，怎样去除重复，
要求时间复杂度为O(n)，空间复杂度为O(1).

//下面的思路没问题，但算法有问题，修正后的算法见后面.

/// <summary>
/// 需要除掉重复的整数的数组，注意这里我没有处理负数情况，
/// 其实负数情况只要先用0快排分一下组，然后各自用以下算法进行处理即可。
/// 另外因为是整数，这里没考虑32位符号位，只考虑31位。
/// 题目分析：从要求来看，如果一个数组是排好序的，除掉重复就很简单，因此就转换成了
/// 排序算法寻找，这种算法需要满足：线性时间，常量内存，原地置换。但纵观这么多算法，比较排序肯定不行，
/// 那么就只有基数排序，桶排序和计数排序，但基数排序依赖于位排序，而且要求位排序是稳定的，
/// 且不能过多使用辅助空间，计数排序排除，因为计数排序无法原地置换，桶排序也需要辅助空间，所以最后考虑用
/// 基数排序。但问题是如何选择位排序，因为位上只有0和1，因此有其特殊性，使用快排的分组就可以达到线性，
/// 但问题是这种算法虽然是线性，原地置换，但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考，
/// 发现，如果从高位开始排序，假设前K位是排好的，对K+1进行排序时，只针对前K位的相同的进行，前K位不相同，也不可
/// 能相等，第K+1位也不影响结果，而前K位相同的排序，就不怕快排的不稳定了，因为这个不稳定不会影响到最终结果。
/// 下面就是算法：
/// </summary>
/// <param name="A"></param>
private void BitSortAndDelRepeatorsA(int[] A)
{
//获取数组长度
int theN = A.Length;
//从高位到低位开始排序，这里从31位开始，32位是符号位不考虑，或者单独考虑。
for (int i = 31; i >= 1; i--)
{
//当前排序之前的值，只有该值相同才进行快排分组，如果不相同，则重新开始另外一次快排
//这很关键，否则快排的不稳定就会影响最后结果.
int thePrvCB = A[0] >> (i) ;
//快排开始位置,会变化
int theS = 0;
//快排插入点
int theI = theS;
//整数基元，就选择快排开始位置的数.
int theAxNum = A[theI];
//2进制基数，用于测试某一位是否为0
int theBase = 1 << (i-1);
//位基元，
int theAxBit = (theAxNum >> (i-1)) & 1;//(A[theI] & (theBase)) > 0 ? 1 : 0;
//分段快排，但总体上时间复杂度与快排分组一样.
for (int j = 1; j < theN; j++)
{
//获取当前数组值的前面已拍过序的位数值。
int theTmpPrvCB = A[j] >> (i);
//如果前面已排过的位不相同，则重新开始一次快排.
if (theTmpPrvCB != thePrvCB)
{
A[theS] = A[theI];
A[theI] = theAxNum;
theS = j;
theI = theS;
theAxNum = A[theI];
theAxBit = A[theI] & theBase;
thePrvCB = theTmpPrvCB;
continue;
}
//如果相同，则按快排处理
int theAJ = (A[j] >> (i - 1)) & 1;//(A[j] & (theBase)) > 0 ? 1 : 0;
if (theAJ <= theAxBit)
{
theI++;
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
}
}
//注意最后一次交换。
A[theS] = A[theI];
A[theI] = theAxNum;
}
}

除掉重复数:只要对上述排序结果进行一次遍历处理即可.

private int[] DeleteRepeatedInt(int[] A)
{
int N = A.Length;
//从低位到高位进行计数排序,因为是整数，这里假设都是正数.
for (int i = 1; i <= 32; i++)
{
CountSort2(A, i);
}
//除掉重复的数
int thePreNum = int.MinValue;
List<int> theRet = new List<int>();
for (int i = 0; i < N; i++)
{
if (A[i] != thePreNum)
{
theRet.Add(A[i]);
thePreNum = A[i];
}
}
return theRet.ToArray();
}

===================================================

排序算法修正部分

/// <summary>
/// 需要除掉重复的整数的数组，注意这里我没有处理负数情况，
/// 其实负数情况只要先用0快排分一下组，然后各自用以下算法进行处理即可。
/// 另外因为是整数，这里没考虑32位符号位，只考虑31位。
/// 题目分析：从要求来看，如果一个数组是排好序的，除掉重复就很简单，因此就转换成了
/// 排序算法寻找，这种算法需要满足：线性时间，常量内存，原地置换。但纵观这么多算法，比较排序肯定不行，
/// 那么就只有基数排序，桶排序和计数排序，但基数排序依赖于位排序，而且要求位排序是稳定的，
/// 且不能过多使用辅助空间，计数排序排除，因为计数排序无法原地置换，桶排序也需要辅助空间，所以最后考虑用
/// 基数排序。但问题是如何选择位排序，因为位上只有0和1，因此有其特殊性，使用快排的分组就可以达到线性，
/// 但问题是这种算法虽然是线性，原地置换，但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考，
/// 发现，如果从高位开始排序，假设前K位是排好的，对K+1进行排序时，只针对前K位的相同的进行，前K位不相同，也不可
/// 能相等，第K+1位也不影响结果，而前K位相同的排序，就不怕快排的不稳定了，因为这个不稳定不会影响到最终结果。
/// 下面就是算法：
/// </summary>
/// <param name="A"></param>
private void BitSortAndDelRepeatorsA(int[] A)
{
//获取数组长度
int theN = A.Length;
//从高位到低位开始排序，这里从31位开始，32位是符号位不考虑，或者单独考虑。
for (int i = 31; i >= 1; i--)
{
//当前排序之前的值，只有该值相同才进行快排分组，如果不相同，则重新开始另外一次快排
//这很关键，否则快排的不稳定就会影响最后结果.
int thePrvCB = A[0] >> (i) ;
//快排开始位置,会变化
int theS = 0;
//快排插入点
int theI = theS-1;
//2进制基数，用于测试某一位是否为0
int theBase = 1 << (i-1);
//位基元始终为0，
int theAxBit = 0;

//分段快排，但总体上时间复杂度与快排分组一样.
for (int j = 0; j < theN; j++)
{

//获取当前数组值的前面已拍过序的位数值。
int theTmpPrvCB = A[j] >> (i);
//如果前面已排过的位不相同，则重新开始一次快排.
if (theTmpPrvCB != thePrvCB)
{
theS = j;
theI = theS - 1;
theAxBit = 0;
thePrvCB = theTmpPrvCB;
j--;//重新开始排，回朔一位.
continue;
}
//如果前面的数相同，则寻找第1个1,thI指向其
//如果相同，则按快排处理
int theAJ = (A[j] & (theBase)) > 0 ? 1 : 0; ;//(A[j] & (theBase)) > 0 ? 1 : 0;(A[j] >> (i - 1)) & 1
//如果是重新开始排，则寻找第1个1，并人theI指向其.这可以减少交换，加快速度.
if (theI < theS)
{
if (theAJ == 0)
{
continue;
}
theI = j;//Continue保证J从theI+1开始.
continue;
}
//交换.
if (theAJ <= theAxBit)
{
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
theI++;
}
}
}
}

经过测试，算法复杂度<32*n。

后记：其实这个面试题的实用价值还是非常大的，这里是整数，如果是字符串排序也可以采用类似算法，而且空间要求比较小。

声明：该算法是本人的原创算法，转载请注明出处，谢谢！

注,本算法也不是稳定的.

另外：面试题集锦，大家可以去July的博客看看，会很有收获：http://blog.csdn.net/v_JULY_v