CSharp solution with O(m)


  • 0
    S

    First, let's get the total column number. Assume the input character array is in length m and the input row number is n. The offset between two characters in two full columns will be n + 1. Also, the minimum value for column number will be 1. Then the column number should be m / (n + 1) + 1.
    There will be a letter in the middle between two columns. The row index for the middle letter will be n / 2.

            private char[] ZigZag(string input, int row)
            {
                int offset = row + 1;
                int colNum = input.Length / offset + 1;
                int zigZagIndex = row / 2;
                char[] result = new char[input.Length];
                int resultIndex = 0;
                for (int i = 0; i < row; i++)
                {
                    for (int j = 0; j < colNum; j++)
                    {
                        int index = i + j * offset;
                        if (index >= input.Length)
                        {
                            break;
                        }
    
                        result[resultIndex] = input[index];
                        resultIndex++;
    
                        if (i == zigZagIndex)
                        {
                            int nextIndex = index + (row - zigZagIndex);
                            if (nextIndex < input.Length)
                            {
                                result[resultIndex] = input[nextIndex];
                                resultIndex++;
                            }
                        }
                    }
                }
    
                return result;
            }
    

    The time complexcity will be O(n) = n * m / n = m. Space complexity is O(m).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.