分区标签问题的空间复杂性

问题描述 投票:1回答:1

给出了一个由小写字母组成的字符串S.我们希望将此字符串分成尽可能多的部分,以便每个字母最多出现在一个部分中,并返回表示每个部分大小的整数列表。

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]

说明:分区是“ababcbaca”,“defegde”,“hijhklij”。这是一个分区,因此每个字母最多只出现一个部分。

像“ababcbacadefegde”,“hijhklij”这样的分区是不正确的,因为它将S分成更少的部分。

以下是针对上述问题的代码:

class Solution {
public List<Integer> partitionLabels(String S) {

    char[] st = S.toCharArray();
    int k=0,c=0;
    List<Integer> res = new ArrayList<Integer> ();
    Set<Integer> visited = new HashSet<Integer> ();

    for(int i=0 ; i<st.length ; i++)
    {
        int idx = S.lastIndexOf(st[i]);
        if(visited.add(i) && idx>i && idx>k)
        {
            k = Math.max(k,idx);
            visited.add(k);

        }
        else if(i == k)
        {
            res.add(i-c+1);
            c=i+1;
            k++;
        }
    }

    return res;

}
}

上面的代码在O(n)中起作用并且上面代码的时间复杂度,因为它访问每个元素一次。

但是空间复杂性是多少?由于我使用的是一个大小与字符串S相同的Char数组和一个Max的大小可以是字符串S大小的Set,它是否也是O(n)?

java time-complexity space-complexity memory-efficient
1个回答
0
投票

由于您只使用一维数组并列出空间复杂度为O(n)。

但你的时间复杂度是O(n²),因为S.lastIndexOf(st[i]);是O(n)。

如果你还想要时间为O(n),你必须预处理一次字符串(= O(n))以确定每个字符的最后一次出现,f.i。用地图来保持检索时间O(1)。

© www.soinside.com 2019 - 2024. All rights reserved.