返回顶部

收藏

腾讯面试题(除掉N个整数中重复数)解题(线性时间,原地置换排序算法)(C#)

更多
    //下面的思路没问题,但算法有问题,修正后的算法见后面.
        /// <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++;
                    }
                }
            }
        }

                                经过测试,算法复杂度&lt;32*n。

后记:其实这个面试题的实用价值还是非常大的,这里是整数,如果是字符串排序也可以采用类似算法,而且空间要求比较小。 声明:该算法是本人的原创算法,转载请注明出处,谢谢! 注,本算法也不是稳定的.

标签:面试题,腾讯,排序算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2013-06-18 21:52:51Java排序算法大全 by p5soft
  2. 2014-01-29 19:52:31睡眠排序法-objective C版 by 跳跳虎
  3. 2014-03-06 16:16:16C++快速排序算法,用到了函数指针 by lucasli
  4. 2014-04-22 12:17:24睡眠排序法-java版 by sdcool
  5. 2014-05-28 13:10:35猴子吃桃问题 by 童学芬
  6. 2014-06-19 15:20:54C++ 归并排序算法 by qqmmcc
  7. 2014-07-09 12:50:59打印N阶(N<=20)螺旋矩阵 by aiheng1988
  8. 2014-08-07 10:08:19C语言算法之归并排序代码 by 睡到自然醒
  9. 2014-09-02 12:39:36报数杀人 by niutao.linux
  10. 2014-09-19 12:09:17睡眠排序法 - ruby版 by 永明
  11. 2018-03-30 21:56:50java自动识别用户上传的文本文件编码 by Hugh

发表评论