c++ - 正确地完成了一个类似竞争的问题，但需要帮助来提高其效率

Question

问题很简单。我得到了 N - 数字中的位数，然后是数字的 N 位。我需要精确地进行一位数字转换并获得尽可能高的数字。我确实正确地解决了这个问题(如给出了正确的数字)，但据我所知它将达到 1 秒时间限制。如何提高程序的效率，使其在 N <= 10^6 的 1 秒时间限制下。堆栈溢出的新内容，请告诉我我是否做错了什么 提出问题以便我可以解决它。谢谢。这是我的解决方案:

主要:

int n;
cin >> n;
int a[n+1];
for(int i=0;i<n;++i)
    cin >> a[i];
int maxofarray1;
bool changeHappened=false;
bool thereAreTwoSame=false;
for(int i=0;i<n;++i) //changing the two digits to make the highest number if possible
{
    maxofarray1=maxofarray(a,i+1,n);
    if(a[i]<maxofarray1)
    {
        int temp=a[a[n]];
        a[a[n]]=a[i];
        a[i]=temp;
        changeHappened = true;
        break;
    }
}

for(int i=0;i<n;++i) //need to check if there are two of the same digit so I can change 
//those two making the number the same instead of making it lower
    for(int j=i+1;j<n;++j)
        if(a[i]==a[j])
        {
            thereAreTwoSame=true;
            break;
        }

if(!changeHappened) //if the change has not been yet made, either leaving the number as is 
//(changing two same numbers) or changing the last two to do as little "damage" to the number
{
    if(!thereAreTwoSame)
    {
        int temp=a[n-1];
        a[n-1]=a[n-2];
        a[n-2]=temp;
    }
}
for(int i=0;i<n;++i)
    cout << a[i] << " ";
return 0;

最大数组:

int maxofarray(int a[], int i,int n) //finding the maximum of the array from i to n
{
    int max1=0;
    int maxind;
    for(int j=i;j<n;++j)
    {
        if(max1<a[j])
        {
            max1=a[j];
            maxind=j;
        }
    }
    a[n]=maxind; //can't return both the index and maximum (without complicating with structs) 
    //so I add it as the last element
    return max1;
}

Answer 1

您的代码中的问题在于复杂性。我不完全理解你的算法，但嵌套循环是一个危险信号。您应该重新考虑您的整体策略，而不是尝试改进代码的零碎部分。

我们首先假设数字 9 确实出现在数字中。考虑数字是

9...9 c ...9...

其中 9...9 是全部为 9 的前导数字(可能没有)。我们不能通过交换其中之一来使数字更大。

c 是第一个数字 !=9，即我们可以在其中放置 9 以获得更大的数字。 9 是放在这个位置时使数字最大的数字。

Last, ...9... 表示最后一次出现的数字 9 以及包含该数字的数字。此后 9 不再出现其他 9。虽然我们通过替换 c 来增加数字，但替换 9 时数字会变小，因此我们必须选择最后一个。

对于一般情况，只需要再执行一小步。这是一个粗略的草图:

 std::array<size_t,10> first_non_appearance;
 std::array<size_t,10> last_appearance;

 size_t n;
 std::cin >> n;
 std::vector<int> number(n);
 for (size_t i=0;i <n;++i) {
     std::cin >> a[i];
     for (int d=0;d<10;++d) {
         // keep track of first and last appearance of each digit
     }
 }

 size_t first = 0;
 size_t second = 0;
 for (int d=0;d<10;++d) {
      // determine biggest digit that appeared and use that
 }
 std:swap( a[first],a[last] );

它并不完整，可能需要处理特殊情况(例如只有一位数字的数字)，但我希望它有所帮助。

PS:您使用的是可变长度数组 (int a[n+1];)，这不是标准 C++。在 C++ 中，当您仅在运行时知道大小时，您应该使用 std::vector(当大小已知时，应该使用 std::array)。