My accepted answer in java, is it cost O(n) or O(n^2)???


  • 0
    J

    I use a StringBuffer, I don't know whether the method deleteCharAt() cost O(1) or O(n).

        public class Solution {
        public String getPermutation(int n, int k) {
            if(n > 9) return"";
            if(n == 1) return "1";
            int [] num = new int[n+1];
            num[0] = 1;
            for(int i = 1;i<=n;i++)
                num[i] = num[i-1]*i;    // store the factor
            k = k-1;
            k = k%num[n];
            StringBuffer numStr = new StringBuffer("123456789");
            StringBuffer res = new StringBuffer();
            for(int i=n-1;i>=0;i--)
            {
                int curNum = k/num[i];
                res.append(numStr.charAt(curNum));
                numStr.deleteCharAt(curNum);
                k = k - curNum*num[i];
            }
            return res.toString();
        }
    }

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    V

    Time complexity is neither O(n^2) nor O(n), due to a single reason that the input number n is fixed in between the range [1,9]. String Buffer deleteCharAt() has amortized constant time.


  • 0
    Q

    The delete operation is O(n), so it makes your algorithm O(n^2). It doesn't affect a lot because n wont grow larger than 15 otherwise k will overflow the capacity of int.


Log in to reply
 

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