确定给定代码的时间和空间复杂度

debugcn 发表于 Dev

苏伯汉索尼

我想为这个问题写代码：

给定一个字符串，请在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);
    }
}

实际上，我正在将一个字符与其他字符进行比较，如果发现它们相等，则用空格替换找到的字符。最后，删除字符串中的所有空格。

我有一个基本的了解，因为必须使用两个for循环，所以它必须是O（n ^ 2）实现（相对于时间）。如何修改O（n）时间和O（1）空间复杂度的代码？

或者换句话说，O（1）空间要求表示什么？我应该使用一个for循环而不是两个来满足时间要求吗？

索力士

O（n）表示没有嵌套的循环，而O（1）表示输入需要恒定的存储空间。

如果将输入字符串限制为全ASCII，则此问题非常简单。

`
    boolean[] counter = new boolean[256];
    StringBuilder sb = new StringBuilder(input);
    for (int i = 0; i < sb.length(); i++) {
        if (counter[(int) input.charAt(i)]) {
            sb.setCharAt(i, ' ');
        }
        counter[(int) input.charAt(i)] = true;
    }
`

但是，如果输入不是ASCII而是Unicode，则无法在O（1）空间中求解。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。