[qsort+self-defined-comparefunc]Share my c++ solutions FYI


  • 0
    G
    class Solution {
    public:
        string largestNumber(vector<int> &num) {
            if(num.empty()) return "";
            if(num.size()==1){
                char ch[30]={0};
                sprintf(ch,"%d",num[0]);
                return (string)ch;
            }
            
            quicksort(num,0,num.size()-1);
            
            string result="";
            
            for (int i=0;i<num.size();i++){
                char ch[30]={0};
                sprintf(ch,"%d",num[i]);
                result += ch;
            }
            
            return (result[0]=='0')?"0":result;
            
        }
        
        void quicksort(vector<int> &num,int l,int r){
            if(l<r) {
                int p = partition(num,l,r);
                quicksort(num,l,p-1);
                quicksort(num,p+1,r);
            }
        }
        
        int partition(vector<int> &num,int l,int r){
            if (l==r) return l;
            swap(num[l],num[l+(rand()%(r-l))]);
            int pivot = num[l];
            int i = l;
            int j = l;
            while(j<r){
                j++;
                if(comp(num[j],pivot)>0){
                    i++;
                    swap(num[i],num[j]);
                }
            }
            swap(num[i],num[l]);
            return i;
        }
        
        char comp(int a,int b){
            if (a==b) return 0;
            char ch_a[30] = {0};
            char ch_b[30] = {0};
            sprintf(ch_a,"%d%d",a,b);
            sprintf(ch_b,"%d%d",b,a);
            int i = 0;
            while (ch_a[i]!='\0' && ch_b[i]!='\0' && ch_a[i]==ch_b[i]) i++;
            return ch_a[i] - ch_b[i];
        }
    };
    

    Easily understandable, is there anything i can simplify without using vector.sort or else method somewhat cheating OJ?


Log in to reply
 

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