我如何优化我的代码从O(n ^ 2)到nlog(n) [英] How can I optimize my code from O(n^2) to nlog(n)

问题描述

给出一个数字数组，以产生最大值的方式排列它们.例如，如果给定的数字为{54，546，548，60}，则排列6054854654给出最大值.并且如果给定的数字为{1、34、3、98、9、76、45、4}，则排列998764543431给出最大值.

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

因此，提供的函数声明为

So, the provided function declaration is

string printLargest(vector<string> &arr)

下面提供了我编写的解决方案.

The solution that I wrote is provided below.

string printLargest(vector<string> &arr) {
    for (int i=0; i<arr.size()-1; i++) {
        for (int j=i+1; j<arr.size(); j++) {
            string y = arr[i] + arr.at(j);
            string z = arr[j] + arr[i];
            if (z>y) swap(arr[j], arr[i]);
        }
    }
    string y="";
    for(string x:arr) y +=x;
    return y;
}

在线编译器显示已超过时间限制" 请优化您的代码，然后再次提交.我认为我的解决方案取O(n ^ 2).预期时间复杂度:O(NlogN)，如何优化代码?

The online compiler says "Time Limit Exceeded" Please optimize your code and submit again. I think my solution take O(n^2). Expected Time Complexity: O(NlogN), How can I optimize my code?

推荐答案

手工解决这个问题，我要做的是取以序列中最高位数开头的数字，对吗?因此，换句话说，我要手动执行的操作是按照此标准对它们进行排序，然后附加它们.
只要您能够描述标准，就可以将分类标准作为自定义比较器，而已成为一种排序算法.

Solving this by hand, what I'd do is to take the numbers which start with the highest digits in their sequences, right? So, in other words, what I'd do by hand is to sort them by this criterion and then appending them.
As soon as you are able to describe the criterion, this becomes nothing more than a sorting algorithm, with the criterion as a custom comparator.

所以基本上，最终，代码看起来可能像这样:

So basically, in the end, the code can look somewhat like:

inline bool better_digits(const string& a, const string& b);

string print_largest(vector<string> data)
{
    std::sort(data.begin(), data.end(), better_digits); // sort
    string result = std::accumulate(data.begin(), data.end(), std::string{}); // append
    return result;
}

换句话说，我做的和您已经做的一样，但是有了更好的排序算法，只需相信 std :: sort 是有效的(就是这样).无需重新发明轮子.

In other words, I did the same as you already did, but with a better sorting algorithm, simply trusting that std::sort is efficient (which it is). No need to reinvent the wheel.

注意:带有 std :: accumulate 的行需要C ++ 20.否则，只需像在自己的代码中那样使用循环来追加.
另外，我从输入中删除了引用，以避免该函数产生副作用，但是如果允许的话，请务必这样做.

Note: the line with std::accumulate requires C++20. Otherwise, simply append by using a loop like you did in your own code.
Also, I removed the reference from the input to avoid the function having a side effect, but if it is allowed to, do that by all means.

剩下要做的就是定义更好的数字.为此，我们可以使用您已经做过的事情以及TUI爱好者也使用过的事情:

The only thing left to do is to define better_digits. For that, we can use what you already did and what TUI lover also used:

inline bool better_digits(const string& a, const string& b)
{
    return a+b > b+a;
}

请注意，我没有将自己的变体与TUI爱好者的变体进行比较.那将被证明是非常有趣的.我发布了我的文章是因为我认为它更具可读性，但TUI爱好者变体可能会更轻松地提高效率.(两者都是Θ(nlogn)，但总体因素也很重要.)

Note that I haven't compared my variant with that of that of TUI lover. That would prove to be quite interesting. I posted mine because I think it is more readable, but TUI lovers variant might easily be more efficient. (Both are Θ(nlogn), but the overall factor also matters.)

这篇关于我如何优化我的代码从O(n ^ 2)到nlog(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！