Is there a O(n) time solution?


  • 0
    Z

    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 {
    public:
        int getDig(int num, int i){
            string s=std::to_string(num);
            if(i>s.size()-1){
                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;
            while(maxNum){
                maxNum/=10;
                m++;
            }
            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.