1

Given a string, move all digit elements to end of string. While moving elements, keep the relative order of all positioned elements same.

For example, if the given string is

a1b2c3d4e5f6g7h8i9j1k2l3m4

convert it to

abcdefghijklm1234567891234

in-place and in O(n) time complexity.

I got a different result

abcdefghijklm7481951326324

Also I failed for testing another string

aHR0cDovL3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9hbi1pbi1wbGFjZS1hbGdvcml0aG0tZm9yLXN0cmluZy10cmF

Code:

    static string s = "a1b2c3d4e5f6g7h8i9j1k2l3m4";
    static void Main(string[] args)
    {
        char[] input = s.ToCharArray();
        string output = arrangeList(input);
        Console.WriteLine(output);
        Console.WriteLine("Another test");
        s = "aHR0cDovL3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9hbi1pbi1wbGFjZS1hbGdvcml0aG0tZm9yLXN0cmluZy10cmF";
        input = s.ToCharArray();
        output = arrangeList(input);
        Console.WriteLine(output);
        Console.Read();
    }

    private static string arrangeList(char[] x)
    {
        for (int i = 1; i < x.Length - 1; i++)
        {
            int j = i + 1;
            while (j < x.Length)
            {
                if ( (x[j] > '0' && x[j] < '9') && x[i] > '9')
                {
                    swap(x, i, j); j++;
                    break;
                }
                if ( (x[i] > '0' && x[i] < '9') && x[j] > '9')
                {
                    swap(x, i, j); j++;
                    break;
                }
                j++;
            }
        }
        return new string(x);
    }
    private static void swap(char[] a, int i, int j)
    {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
  • 2
    Why is it important that it is in place? – Alex Siepman Mar 09 '14 at 19:06
  • Never mind, yeah. It doesn't matter. Sorry for it. But I wish that there is another in-place algorithm. –  Mar 09 '14 at 19:07
  • Why down vote? Please provide me a reason. Originally it was an in place alrorithm question at http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/. I just modified it. –  Mar 09 '14 at 20:08
  • @Love - Why did you tag the question with "linq", but give the answer to a non-linq solution? Especially when you have two excellent linq solutions? – Enigmativity Mar 10 '14 at 01:46
  • @Enigmativity, I am not sure linq's complexity. I hope there is a generic algorithm if I use other language alough tagged c# and linq. –  Mar 10 '14 at 01:51
  • @Enigmativity: One of the LINQ solutions doesn't work, and the other has O(n log n) complexity. – Jim Mischel Mar 10 '14 at 03:36
  • possible duplicate of [Move all odd positioned element to left half and even positioned to right half in-place](http://stackoverflow.com/questions/12338654/move-all-odd-positioned-element-to-left-half-and-even-positioned-to-right-half-i) – minhaz Feb 17 '15 at 05:04

4 Answers4

3

With Linq

var input = "a1b2c3d4e5f6g7h8i9j1k2l3m4";
var output = String.Join("", input.GroupBy(c => char.IsDigit(c))
                                  .OrderBy(x => x.Key) //Always 2 items to sort. Not O(N*logN)
                                  .SelectMany(g => g));
L.B
  • 114,136
  • 19
  • 178
  • 224
  • @NiklasB. `My definition`? Are you *Love* or *NiklasB* ? BTW: you convert your string to char array. So you don't do it in-place too. – L.B Mar 09 '14 at 18:58
  • Well since OP has revised his requirement of in-placeness, I removed my comments as they are no longer relevant. +1 for a pragrmatic approach – Niklas B. Mar 09 '14 at 19:08
  • The problem with this solution is that if the beginning string is `"1ab2c3d4e5f6g7h8i9j1k2l3m4"`, the numbers are at the front of the string rather than at the end. – Jim Mischel Mar 10 '14 at 00:10
  • This is easily fixed with a `.OrderBy(x => x.Key)` after the `GroupBy`. This wouldn't be O(n) though, but how big could the input string to make the efficiency an issue? – Enigmativity Mar 10 '14 at 03:43
1

You can build it in a character array pretty easily by working from the back to copy digits and from the front to copy letters. That is:

var input = "a1b2c3d4e5f6g7h8i9j1k2l3m4";
int ixLetter = 0;
int ixDigit = input.Length - 1;
int oxLetter = 0;
int oxDigit = input.Length - 1;

char[] output = new char[input.Length];
while (ixDigit >= 0)
{
    if (char.IsDigit(input[ixDigit]))
    {
        output[oxDigit] = input[ixDigit];
        --oxDigit;
    }
    if (!char.IsDigit(input[ixLetter]))
    {
        output[oxLetter] = input[ixLetter];
        ++oxLetter;
    }
    --ixDigit;
    ++ixLetter;
}

string result = new string(output);

This does two passes over the string, one from the front and one from the back. Complexity is linear, thus O(n).

Now, doing it in a single pass ... I'd have to think a bit about that.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • this algorithm violates in-place property. size of the output arrays is n, so this is O(n) space complexity. – minhaz Feb 17 '15 at 05:03
1

This works, uses linq, and has O(n) time complexity:

var input = @"123vcvcv00191pololo";
var array =
    input
        .ToCharArray()
        .Where(c => !Char.IsDigit(c))
        .Concat(
            input
                .ToCharArray()
                .Where(c => Char.IsDigit(c)))
        .ToArray();
var output = new String(array);

Console.Write(output);
// vcvcvpololo12300191
Enigmativity
  • 113,464
  • 11
  • 89
  • 172
0

using linq's OrderBy as shown should move all the digits to the end of the string/char[] in the order in which they appear in the string.

var input  = @"123vcvcv00191pololo";
var array  = input.ToCharArray().OrderBy(c => Char.IsDigit(c)).ToArray();
var output = new String(array);

Console.Write(output);
//vcvpololo12300191
Ismail Hawayel
  • 2,167
  • 18
  • 16