Is there a O(n) time solution?

  • 0

    I see most posts use std::sort( ) which is O(nlgn). I tried to use a modified radix sort but failed with the last two tests and I don't know the reason. Could someone point it out? Is there a O(n) solution possible??

    class Solution {
        int getDig(int num, int i){
            string s=std::to_string(num);
                if(s.back()-s[0]==1) return s[0]+1-'0';
                else return s[0]-'0';
            return s[i]-'0';
        void countSort(vector<int>& nums, int x)
            vector<int> res(nums.size(),0); 
            int i, count[11] = {0};
            for (i = 0; i < nums.size(); i++) count[ getDig(nums[i], x) ]++;
            for (i = 0; i <=10; i++) count[i] += count[i - 1];
            for (i = nums.size() - 1; i >= 0; i--){
                res[count[ getDig(nums[i], x) ] - 1] = nums[i];
                count[ getDig(nums[i], x) ]--;
            for (i = 0; i < nums.size(); i++) nums[i] = res[i];
        string largestNumber(vector<int>& nums) {
            int maxNum=nums[0];
            for(int i=1;i<nums.size();i++) maxNum=max(maxNum,nums[i]);
            int m=0;
            for (int x = m-1; x>=0; x--) countSort(nums, x);
            string res="";
            for (int i=nums.size()-1;i>=0;i--) res+=std::to_string(nums[i]);
            while(res[0]=='0'&&res.size()>1) res.erase(res.begin());
            return res;

Log in to reply

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