题目:一个大小为N的数组,里面是N个整数,怎样去除重复,
要求时间复杂度为O(n),空间复杂度为O(1).
转自:http://blog.csdn.net/hawksoft/article/details/6867493
//下面的思路没问题,但算法有问题,修正后的算法见后面. /// <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++; } } } }
经过测试,算法复杂度后记:其实这个面试题的实用价值还是非常大的,这里是整数,如果是字符串排序也可以采用类似算法,而且空间要求比较小。
声明:该算法是本人的原创算法,转载请注明出处,谢谢!
注,本算法也不是稳定的.