algorithm - Run length encoding using O(1) space

Question

Can we do the run-length encoding in place(assuming the input array is very large) We can do for the cases such as AAAABBBBCCCCDDDD A4B4C4D4

But how to do it for the case such as ABCDEFG? where the output would be A1B1C1D1E1F1G1

Answer 1

我的第一个想法是从末尾开始编码，所以我们将使用空闲空间（如果有的话），然后我们可以将编码后的数组移到开头。这种方法的一个问题是它不适用于AAAAB，因为没有可用空间（A4B1 不需要它），我们将尝试在第一次迭代时编写 AAAAB1。

下面是更正的解决方案：（假设序列是 AAABBC）

1. 用两个或更多元素对所有组进行编码，其余的保持不变（这不会增加数组的长度）-> A3_B2C
2. 第一步后将所有内容向右移动以消除空格-> _A3B2C
3. 从头开始编码数组（当然重用已经编码的组）-> A3B2C1

每一步都是 O(n)，据我所知，只需要恒定的额外内存。

限制：

1. 不支持数字，但是正如 Petar Petrov 提到的那样，无论如何都会产生解码问题。
2. 我们需要某种“空”字符，但这可以通过添加零来解决：A03 而不是 A3_

Answer 2

C++ 解 O(n) 时间 O(1) 空间

string runLengthEncode(string str)
{
    int len = str.length();
    int j=0,k=0,cnt=0;
    for(int i=0;i<len;i++)
    {
        j=i;
        cnt=1;
        while(i<len-1 && str[i]==str[i+1])
        {
            i++;
            cnt++;
        }
        str[k++]=str[j];
        string temp =to_string(cnt);
        for(auto m:temp)
            str[k++] = m;
    }
    str.resize(k);
    return str;
}

Answer 3

null 用于指示哪些项目是空的，将被忽略进行编码。您也不能对数字进行编码（AAA2222 => A324 => 324 乘以 'A'，但它是 A3;24）。您的问题会引发更多问题。

这是 C# 中的“解决方案”

public static void Encode(string[] input)
{
    var writeIndex = 0;

    var i = 0;
    while (i < input.Length)
    {
        var symbol = input[i];
        if (symbol == null)
        {
            break;
        }

        var nextIndex = i + 1;

        var offset = 0;
        var count = CountSymbol(input, symbol, nextIndex) + 1;
        if (count == 1)
        {
            ShiftRight(input, nextIndex);
            offset++;
        }

        input[writeIndex++] = symbol;
        input[writeIndex++] = count.ToString();

        i += count + offset;
    }

    Array.Clear(input, writeIndex, input.Length - writeIndex);
}

private static void ShiftRight(string[] input, int nextIndex)
{
    var count = CountSymbol(input, null, nextIndex, (a, b) => a != b);
    Array.Copy(input, nextIndex, input, nextIndex + 1, count);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex)
{
    return CountSymbol(input, symbol, nextIndex, (a, b) => a == b);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex, Func<string, string, bool> cmp)
{
    var count = 0;

    var i = nextIndex;
    while (i < input.Length && cmp(input[i], symbol))
    {
        count++;
        i++;
    }

    return count;
}

Answer 4

第一种解决方案不处理单个字符。例如 - “嗨！” 不管用。我使用了完全不同的方法，使用 'insert()' 函数就地添加。这会处理所有事情，无论总“相同”字符是 > 10 还是 > 100 还是 = 1。

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    string name = "Hello Buddy!!";
    int start = 0;
    char distinct = name[0];
    for(int i=1;i<name.length()+1;){
        if(distinct!=name[i]){
            string s = to_string(i-start);
            name.insert(start+1,s);
            name.erase(name.begin() + start + 1 + s.length(),name.begin() + s.length() + i);
            i=start+s.length()+1;
            start=i;
            distinct=name[start];
            continue;
        }
        i++;
    }
    cout<<name;
}

如果您发现任何不正确的地方，请建议我。

Answer 5

O(n)，就地 RLE，我想不出比这更好的了。如果字符出现仅 1，则不会放置数字。如果字符出现 11 次，也会放置 a9a2。

void RLE(char *str) {
int len = strlen(str);
int count = 1, j = 0;
for (int i = 0; i < len; i++){
    if (str[i] == str[i + 1])
        count++;
    else {
        int times = count / 9;
        int rem = count % 9;
        for (int k = 0; k < times; k++) {
            str[j++] = str[i];
            _itoa(9, &str[j++], 10);
            count = count - 9;
        }
        if (count > 1) {
            str[j++] = str[i];
            _itoa(rem, &str[j++], 10);
            count = 1;
        }
        else 
            str[j++] = str[i];
    }
}
cout << str;

}

I/P => aaabcdeeeefghijklaaaaa

O/P => a3bcde4fghijkla5

Answer 6

 Inplace solution using c++ ( assumes length of encoding string is not more than actual string length):

    #include <bits/stdc++.h>
    #include<stdlib.h>
    using namespace std;

    void replacePattern(char *str)
    {
        int len = strlen(str);
        if (len == 0)
        return;

        int i = 1, j = 1;
        int count;

        // for each character
        while (str[j])
        {
            count = 1;
            while (str[j] == str[j-1])
            {
                j = j + 1;
                count++;
            }

            while(count > 0) {
                int rem = count%10;
                str[i++] = to_string(rem)[0];
                count = count/10;
            }
            // copy character at current position j
            // to position i and increment i and j
            if (str[j])
                str[i++] = str[j++];
        }

        // add a null character to terminate string
        if(str[len-1] != str[len-2]) {
            str[i] = '1';
            i++;
        }
        str[i] = '\0';
    }

    // Driver code
    int main()
    {
        char str[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabccccc";
        replacePattern(str);
        cout << str;
        return 0;
    }