Share my 4 ms C++ solution


  • 0
    F
    class Solution {
    public:
        string largestNumber(vector<int>& nums) {
            int lens = nums.size(), i;
            vector<string> str(lens);
            for(i = 0; i < lens; ++i)
                str[i] = to_string(nums[i]);
            sort(str.begin(), str.end(), cmp);
            string result;
            for(i = 0; i < lens; ++i)
                result += str[i];
            if(result.empty() || result[0] == '0')
                return "0";
            return result;
        }
        
    private:
        static bool cmp(const string &A, const string &B)
        {
            if(A.size() == B.size())
                return A > B;
            int i = -1;
            while(++i < A.size() && i < B.size())
                if(A[i] != B[i])
                    return A[i] > B[i];
            if(i == A.size())
                return cmp(A, B.substr(i));
            else
                return cmp(A.substr(i), B);
        }
    };

  • 0
    K

    My 0ms solution in c, including manual quick sort helper.

    long long join(int p, int q) {
        long long base = 10;
        while (q >= base) {
          base *= 10;  
        }
        return p * base + q;
    }
    int cmp(int p, int q) {
        if (p == q) return 0;
        long long a = join(p, q), b = join(q, p);
        if (a > b) return 1; // 90 > 09
        if (b > a) return -1;
        return 0;
    }
    void sort(int *data, int len) {
        if (len <= 1) return;
        int mid = data[rand() % len];
        int i = 0, j = len-1;
        while (true) {
            while (i <= j && cmp(data[i], mid) < 0) i++;
            while (i <= j && cmp(data[j], mid) > 0) j--;
            if (i > j) {
                sort(data, i);
                sort(data+i, len-i);
                return;
            }
            int t = data[i];
            data[i] = data[j];
            data[j] = t;
            i++, j--;
        }
    }
    char* largestNumber(int* nums, int numsSize) {
      sort(nums, numsSize);
      char *s = (char *)malloc(numsSize * 10 + 1);
      int len = 0;
      for (int i = numsSize - 1; i >= 0; i--) {
          if (len == 0 && nums[i] == 0 && i > 0) continue;
          len += sprintf(s+len, "%d", nums[i]);
      }
      return s;
    }

Log in to reply
 

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