C# 移动第一个重复字符到前面

例如 abcdbbfg 变成 bbbacdfg，要求时间复杂度为N,空间复杂度为1，写了两个方法都未达到要求 :(

 

        static void MoveDupCharToFront(char[] input)
        {
            if (input == null|| input.Length <=1)
            {
                throw new Exception("input can't be empty or less than 2 length");
            }
            int dupCount = 0;
            int x = 0;
            char dupChar = FindFirstDupChar(input);
            char[] result = new char[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == dupChar)
                {
                    dupCount++;
                }
            }

            while (dupCount >0)
            {
                result[x++] = dupChar;
                dupCount--;
            }
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i]!=dupChar)
                {
                    result[x++] = input[i];
                }
            }
            input = result;
        }

        static void MoveDupCharToFront2(char[] input)
        {
            if (input == null|| input.Length <=1)
            {
                throw new Exception("input can't be empty or less than 2 length");
            }
            char dupChr = FindFirstDupChar(input);
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i]== dupChr)
                {
                    for (int j = i; j >0; j--)
                    {
                        input[j] = input[j - 1];
                    }
                    input[0] = dupChr;
                }
            }
        }

        static char FindFirstDupChar(char[] input)
        {
            if (input == null || input.Length ==0)
            {
                throw new Exception("input can't be empty .");
            }
            Hashtable ht = new Hashtable();
            for (int i = 0; i < input.Length; i++)
            {
                if (ht[input[i]] == null)
                {
                    ht.Add(input[i], 1);
                }
                else
                {
                    return input[i];
                }
            }
            throw new Exception("No dup char.");
        }