小编Sho*_*hit的帖子

给定正整数(以数字数组的形式).我们被允许交换给定数字中的一对数字.我们需要返回可以获得的最小可能整数.注意,它应该是一个有效的整数,即不应该包含前导0.

例如:-

1. 93561返回13569
2. 596返回569
3. 10234返回10234
4. 120返回102
5. 10091返回10019
6. 98761111返回18761119

是否有O(n)针对此问题的算法.我想到了几个方法: -

1. 找到分钟.minDIgit给定整数中的digit()(0除外)并将其与MSB交换,如果MSB != minDigit.如果MSB==minDigit,那么找到下一分钟.数字并用最重要但1位数字交换它,依此类推.这可能是O(n^2)最糟糕的情况.
2. 作出array/vector的std::pair数字和索引的,并以递增顺序排序(按数位值;保持低指数的第一匹配数字值).遍历排序的数组.用第一个数字交换MSB.如果最小数字具有相应的索引作为MSB,则交换MSB但是将1个位置与下一个最小数字交换.如果下一个最小数字具有相应的MSB索引但是1个位置,那么交换MSB但是在下一个min处交换2个位置.数字等.这应该是O(nlog(n)).

有人可以建议更好的算法.

更新1: 经过一番思考后,我提出的第二个算法将完美地工作(可能除了少数角落情况,可以单独处理).此外,我可以使用计数排序(根据数字值)对对(数字,索引)进行排序,这是一种稳定的O(n)时间排序.我的论点有缺陷吗？

更新2: 我的第二个算法会工作(虽然有更多的角落情况和0的检查),而且也是O(n)时间counting sort.但是@GaborSch提供的解决方案要简单得多,所以我不会真的为我的算法提供合适的代码.

鉴于k,我们需要写作表格1的k分数之和1/r.

例如,

1. 因为k=2,1可以唯一地写成1/2 + 1/2.
2. 因为k=3,1可以写成1/3 + 1/3 + 1/3或1/2 + 1/4 + 1/4或1/6 + 1/3 + 1/2

现在,我们需要考虑所有这些k分数总和,1并在所有这些集合中返回最高分母; 例如,样本案例2,我们的算法应该返回6.

我在编码竞赛中遇到了这个问题,并且无法提出相同的算法.之后的一些谷歌搜索显示,这些分数被称为埃及分数,但可能它们是一组不同的分数,总计达到一个特定的值(不是这样1/2 + 1/2).此外,当他们的号码受到限制时,我找不到计算埃及分数(如果它们对这个问题都有帮助)的算法k.

#include "iostream"

using namespace std;

int main(int argc, char const *argv[])
{
    int n=100000;
    int cost=6;
    for (int i = 1; i <= n; ++i)
    {
        cout<<cost<<endl;
    }
    return 0;
}

编译并运行在ideone.com上的上述程序(使用SPOJ编译器的在线g ++编译器)会产生运行时错误.当cout注释掉该行时,程序将成功运行.有人能指出相同的原因吗？