179.最大数

🥩堆排序

  堆排序，然后将数字拼接成字符串，但是两个数字之间的比较并不能直接用><来进行。我的方法是定义compare函数，进行比较。compare比较两个数的方法是：比如121，12，那么就比较121|12和12|121的大小

class Solution {
public:
    string largestNumber(vector<int>& a) {
        if(!a.size())
          return "";
        string s;

        //堆排序
        a.insert(a.begin(), -1);
        int n = a.size() - 1;
        for(int i = 2; i <= n; ++i) {
          swim(a, i, n);
        }
        // for(auto x : a) {
        //   cout << x << " ";
        // }
        // cout << endl;
        while(n > 1) {
          swap(a[1], a[n--]);
          sink(a, 1, n);
        }
        // for(auto x : a) {
        //   cout << x << " ";
        // }
        for(int i = 1; i < a.size(); ++i) 
          s += to_string(a[i]);
        int ct = 0;
        for(int i = 0; i < s.size() && s[i] == '0'; ++i) {
          ++ct;
        }
        if(ct == s.size()) return "0";
        return s.substr(ct);
    }

    void swim(vector<int>& a, int k, int n) {
      cout << "swim" << endl;
      int j;
      while(k > 1) {
        j = k /2;
        if(j >= 1 && compare(a[j],a[k]) != 1) break;
        swap(a[j], a[k]);
        k = j;
      } 
    }

    void sink(vector<int>& a, int k, int n) {
      int j ;
      while(k <= n / 2) {
        j = 2 * k;
        if(j + 1 <= n && compare(a[j + 1], a[j]) == -1) ++j;
        if(compare(a[j], a[k]) != -1) break;
        swap(a[j], a[k]);
        k = j;
      }
    }

    int compare(int i, int j) {
      if(i == j) 
        return 0;
      int com = 0, ix = 0, jx = 0, ii = i, jj = j;
      while(ii / 10 > 0) {
        ix++;
        ii /=  10;
      }
      while(jj / 10 > 0) {
        jx++;
        jj /= 10;
      }
      long long ir ,jr;
      jr = j * pow(10, ix + 1) + i;
      ir = i * pow(10, jx + 1) + j;
      // cout << "i, j: " << ir << " " << jr << endl;
      if(ir > jr) return 1;
      else if(jr > ir) return -1;
      else return 0;
    }
};

Accepted

222/222 cases passed (8 ms)

Your runtime beats 91.43 % of cpp submissions

Your memory usage beats 79.45 % of cpp submissions (9.1 MB)

🈶改进

  相比与我将两个数拼在一起比较，更加好的方法是转化为字符串比较

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) {
            return string("0");
        }
        vector<string> strNums(nums.size());
        std::transform(nums.begin(), nums.end(), strNums.begin(), [](int x) {
            return std::to_string(x);
        });

        std::sort(strNums.begin(), strNums.end(), [](const string& x, const string& y) {
            /* x为后面元素，y为前面元素，return true则将x移动到前面 */
            return x + y > y + x;
        });

        return std::accumulate(strNums.begin(), strNums.end(), string());
    }
};