小编sub*_*oni的帖子

我想为这个问题编写代码:

给定一个字符串,在O(n)时间和O(1)空间中删除它的重复项.

现在,我编写了一个代码来删除字符串中的重复项.

public class RemoveDuplicates
{
    public static void main(String args[])
    {
        String input = "aabbccc";
        char[] inputArray = input.toCharArray();
        for(int i=0;i<inputArray.length;i++)
        {
            for(int j=i+1;j<inputArray.length;j++)
            {
                if(inputArray[i] == inputArray[j])
                    inputArray[j] = ' ';
            }
        }
        input = new String(inputArray);
        input = input.replaceAll("\\s+","");
        System.out.println("The String after removing duplicates is : "+input);
    }
}

实际上,我正在拍摄一个角色并与其他人进行比较,如果发现它们相等,则用空格替换找到的角色.最后,删除字符串中的所有空格.

我有一个基本的理解,它必须是O(n ^ 2)实现(关于时间)因为使用两个for循环.如何修改我的代码的O(n)时间和O(1)空间复杂度？

或者换句话说,O(1)空间要求意味着什么？我应该在时间要求中使用单个for循环而不是两个吗？