将数组中指定的前N位移动到数组的最后面

时间：2025-04-15 13:12:14

微软的一道面试算法题：

传入一个数组如 {1,2,3,4,5,6,7}
将数组前面 head的一个子集移到数组末尾end
如input numberOfElements=3，则{1,2,3,4,5,6,7}=>{4,5,6,7,1,2,3}
input numberOfElements=5，则{1,2,3,4,5,6,7}=>{6,7,1,2,3,4,5}
如何写出该算法？

给定方法签名：MoveSubArrayToTheEnd(int[] array, int numberOfElements) 请不要使用FCL提供的类库函数


第一种做法：就是另外申请一个数组，然后把要移动的元素进行一次拷贝，之后将原数组剩下的元素进行前移，在把拷贝的元素放在数组的最后面。（这种方法简单、易想）

第二种方法：就是对数组相应段落的元素进行求逆序运算。（这种方法很巧妙）

C#代码如下所示：

        // 假设^表示逆序
        // A = (1,2,3)    A^ = (3,2,1)
        // B = (4,5,6,7)  B^ = (7,6,5,4)
        // 则：
        // AB = (1,2,3)(4,5,6,7)
        // (A^B^)^ = BA = (4,5,6,7)(1,2,3)
        //
        void MoveSubArrayToTheEnd(int[] array, int numberOfElements)
        {
            (array, 0, numberOfElements);
            (array, numberOfElements,  - numberOfElements);
            (array);
        }


我们可以通过交换数组相应位置的元素，自己实现的方法。

代码如下所示：

　private static void MoveSubArrayToTheEnd(int[] array, int numberOfElements)
        {
            //(array, 0, numberOfElements);
            //(array, numberOfElements,  - numberOfElements);
            //(array);
            ReverseTargetArray(array, 0, numberOfElements);
            ReverseTargetArray(array, numberOfElements,  - numberOfElements);
            ReverseTargetArray(array, 0, );
        }

        ///<summary>
        /// 实现数组相应段落元素的求逆运算
        ///</summary>
        ///<param name="array">操作的目标数组</param>
        ///<param name="index">进行求逆序的起始位置</param>
        ///<param name="length">进行求逆序的元素个数（包括起始位置的那个）</param>
        private static void ReverseTargetArray(int[] array, int index, int length)
        {
            //保证起始下标和求逆元素个数的合法性
            if (index < 0 || length >  || index + length > )
            {
                return;
            }
            int first = index;  //记录求逆的起始元素位置
            int second = length + first - 1;    //记录求逆的终止元素位置

            //循环对换元素（将此区间的元素进行求逆序运算。例如：1234-->4321）
            while (first < second)
            {
                int temp = 0;
                temp = array[first];
                array[first] = array[second];
                array[second] = temp;
                first++;
                second--;
            }
        }

相关文章