c++ - 如何编写算法从数组中的项目构造数字

Question

编辑:我已经按降序对数组进行排序(a[0] 是最大的)

int [n] a;  (n_max = 18)

数组中的每一项都有一个整数，取值范围:0 -> 9。我想从数组中的项目构造2 组数字，这样:

//group A: 
numberA[0] = a[0]*pow(10,0);
numberA[1] = a[0]*pow(10,1) + a[1]*pow(10,0);
numberA[2] = a[0]*pow(10,2) + a[1]*pow(10,1) + a[2]*pow(10,0);
numberA[3] = a[0]*pow(10,3) + a[1]*pow(10,2) + a[2]*pow(10,1) + a[3]*pow(10,0);
numberA[n] = a[0]*pow(10,n-1) +...+ a[n-1]*pow(10,0)

//group B: 
numberB[0] = a[0]*pow(10,0);
numberB[1] = a[0]*pow(10,0) + a[1]*pow(10,1);
numberB[2] = a[0]*pow(10,0) + a[1]*pow(10,1) + a[2]*pow(10,2);
numberB[3] = a[0]*pow(10,0) + a[1]*pow(10,1) + a[2]*pow(10,2) + a[3]*pow(10,3);
numberA[n] = a[0]*pow(10,0) +...+ a[n-1]*pow(10,n-1)

例如，如果我有一个数组[4] = {9,8,7,6}；我会有以下数字:numberA[] = {9 ,98 ,987, 9876} 和 numberB = {6, 76, 876, 9876}

谁能教我一些使用 for 循环、递归或任何机智的算法以及它的时间 + 空间复杂度？

到目前为止我的尝试:

long long int numberA = 0;
vector<long long int>numberAList; 
numberA = num[0]*(pow(10,0));
numberAList.push_back(numberA);
numberA = 0;
for (int i = 0; i < n-1; i++ ){               // complexity: O(logn) & this algorithm is wrong
    for (int j = i+1; j<n-1; j++){
        numberA += num[i]*pow(10,n-1-j);
        cout<<"numberA"<<numberA<<endl;
    }
    numberAList.push_back(numberA);
}

for (int i = 0; i < (n-2); i++ ){
    cout<<numberAList[i]<<" ";
}

根据 user1984 的建议。我做了代码:

long long int numberA=0;
vector<long long int> numberAList;
for (int i = 0; i < n-1 ; i++ ){                  // complexity O(n)
    numberA *= 10;
    numberA += num[i];
    cout<<i<<", numberA: "<<numberA<<endl;
    numberAList.push_back(numberA);
}

for (int i = 0; i < n-1; i++ ){
    cout<<numberAList[i]<<" ";
}

long long int numberB = 0;
vector<long long int> numberBList;                        
for (int i = 0; i < n; i++ ){                           // complexity O(n)
    int j = i+1;
    if (j<n){
        for (j ; j<n; j++ ){
            numberB += num[j]*(pow(10,n-j-1));
        }
        numberBList.push_back(numberB);
        numberB=0;
    }
}

cout<<"numberBlist: "<<endl;
for (int i = 0; i < (n-1); i++ ){
    cout<<numberBList[i]<<" ";
}

该代码适用于短数字；然而，对于大数字，我开始看到一些奇怪的结果，即使在我将数据类型更改为 long long int 之后也是如此。

有人能帮忙吗？

// if input = 94321

numberBlist:
94321 4321 321 21 1
numberAlist:
9 94 943 9432 94321

// but with input = 999999999999999999
numberBlist:
100000000000000016 10000000000000000 999999999999999 99999999999999 9999999999999 999999999999 99999999999 9999999999 999999999 99999999 9999999 999999 99999 9999 999 99 9
numberAlist:
9 99 999 9999 99999 999999 9999999 99999999 999999999 9999999999 99999999999 999999999999 9999999999999 99999999999999 999999999999999 9999999999999999 99999999999999999

Answer 1

这看起来像是一项任务，所以我不打算提供代码，而是提供一种(希望如此)清晰的方法，帮助您以您喜欢的任何语言解决问题。

1. 有一个变量 current 来跟踪你的当前值
2. 有一个数组 res 用于在迭代输入数组 nums 时累积结果。
3. 对于数组 nums 中的每个 nums_i，按照顺序执行以下操作:

• 当前 *= 10
• current += nums_i
• 将电流插入res

就是这样。我认为该方法是不言自明的，但如果您觉得需要更多详细说明，请询问。

根据 OP 最近的编辑更新:要处理任意大小的整数，您有 2 个选择:

1. 使用一个库来处理任意大小的数字运算，比如 gmplib ，并使用与您当前拥有的算法或类似算法类似的算法。
2. 利用您不更改数字基数并采用字符串/字符连接这一事实。如果最后需要将其转换为整数，可以使用库。请注意，这些库使用位操作技术并且已经过优化以非常快地工作。阅读例如 this informative article了解详情。

关于您在大数上运行的测试的注释:“999999999999999999”小于 64 位有符号整数，因此当前算法不应该工作，因为 c++ 中的“long long”保证至少为 64位。我对 C++ 不是很熟悉，但由于并非代码的所有部分都是共享的，所以看看您是否有一个地方可以将大值存储在一些可能溢出的较小数据类型中。