使用循环,如何在整数区间 [n, m] 中查找每个数字的出现次数?
例如:
输入 n,m = [19, 23] = 19, 20, 21, 22, 23
输出应为:
0次出现:1次
出现1次:2次
2次出现:5次
3次出现:1次等
#include <iostream>
using namespace std;
int main()
{
int i, j, z, count, n, m;
cin >>n >>m;
for(int i=0; i<10; i++) // LOOP FOR DIGITS
{
cout << i <<"occurences: ";
count=0;
for(int j=n; j<m; j++) // LOOP INTEGER INTERVAL
{
while (z!=0)
{
z = j % 10; // LAST DIGIT OF FIRST NUMBER IN INTERVAL
if (z == i) count++;
z /= 10;
}
}
cout << count <<" times"<< endl;
}
}
我的代码为每个数字返回 0 次,错误在哪里?
您不需要遍历该范围 10 次。
int n, m;
cin >> n >> m;
counts = int[10];
for(int i = 0; i < 10; ++i) {
counts[i] = 0;
}
for(int j = n; j <= m; j++) {
int z = j;
do {
int digit = z % 10; // LAST DIGIT OF FIRST NUMBER IN INTERVAL
counts[digit]++;
z /= 10;
} while (z != 0);
}
for(int i = 0; i < 10; ++i) {
cout << i << " occurrences " << counts[i] << " times";
}
您可以使用 std::stringstream 获取数字中的每个数字,如下所示:
constexpr int n = 19;
constexpr int m = 23;
std::array<int, 10> digit_count = {0};
for (int i = n; i <= m; i++)
{
std::stringstream s;
s << i;
unsigned char digit;
while (s >> digit) digit_count[digit - '0']++;
}
我看到的一些问题:
z = j % 10;
您需要将 while 循环之外的z
初始化为 j 此外,您还想获取 mod 但不对其进行z
设置。 尝试将结果放入 temp 变量中,而不是放入z
中。
您的 for 循环不包含最后一个数字。for(int j=n; j<m; j++)
应该是j<=m
.
z = j;
while (z!=0)
{
int mod = z % 10; // LAST DIGIT OF FIRST NUMBER IN INTERVAL
if (mod == i) count++;
z /= 10;
}
}
此最终代码给出正确的结果:
#include <iostream>
using namespace std;
int main()
{
int i, j, z, count, n, m;
cin >>n >>m;
for(int i=0; i<10; i++) // LOOP FOR DIGITS
{
cout << i <<" occurences: ";
count=0;
for(int j=n; j<=m; j++) // LOOP INTEGER INTERVAL
{
z = j;
while (z!=0)
{
int mod = z % 10; // LAST DIGIT OF FIRST NUMBER IN INTERVAL
if (mod == i) count++;
z /= 10;
}
}
cout << count <<" times"<< endl;
}
}
19 23
0 occurences: 1 times
1 occurences: 2 times
2 occurences: 5 times
3 occurences: 1 times
4 occurences: 0 times
5 occurences: 0 times
6 occurences: 0 times
7 occurences: 0 times
8 occurences: 0 times
9 occurences: 1 times
基本上,取模运算用于检索任何数字的最低有效数字。将此数字与基数除以将删除最低有效数字,使下一个数字成为新的最低有效数字。
int main(int argc, char *argv[])
{
int radix = 10;
int x, y;
printf("Lower bound: ");
scanf("%d, &x);
printf("Upper bound: ");
scanf("%d, &y);
int digits[radix];
count_digit_occurence(x, y, radix, digits);
int i;
for (i = 0; i < radix; ++i)
{
int occ = digits[i];
printf("%d occurred %d timesn", i, occ);
}
}
void count_digit_occurence(int x, int y, int radix, int digits[radix])
{
int i, n;
for (i = x; i <= y; ++i)
{
n = i;
while (n > 0)
{
++(digits[n % radix]);
n /= radix;
}
}
}
到目前为止,所有答案都提供了算法的复杂性,充其量O(m-n)
,即从n
到m
的距离是线性的。在这里,我提供了一种具有对数复杂性的方法。基本思想是首先考虑每个数字的最后一位数字,然后考虑倒数第二个数字,依此类推。
为了简化代码,我稍微改变了问题并考虑了范围[n, m-1]
,即排除m
。
此范围内有m-n
个数字;如果这是 10 的倍数,则每个最后的数字正好出现(m-n)/10
次。否则,我们必须考虑边缘。以下例程将n
到m-1
范围内所有数字中最后一位数字的出现次数相加count
unit
倍。
void count_last_digits(int n, int m, std::array<int,10> count&, int unit=1)
{
// 1 increment n until it has the same last digit as m
for(int dn=n%10, dm=m%10; n<m && dn!=dm; dn=++n%10)
count[dn] += unit;
// 2 add unit*(m-n)/10 to all counts
if(int cnt = unit*(m-n)/10) // avoid to add nothing
for(int d=0; d!=10; ++d)
count[d] += cnt;
}
有一次,我们数了最后一位数字,我们数了倒数第二位数字,依此类推。首先,我们需要一个只计算单个数字的位数的辅助函数
void count_digits(int x, std::array<int,10> &count, int unit=1)
{
for(; x; x/=10)
count[x%10] += unit;
}
要继续倒数第二个数字,我们首先修剪(使用此辅助函数(间隔,使n
和m
都是 10 的倍数,然后将它们都除以 10,将计数单位乘以 10,然后递归
std::array<int,10> count_all_digits(int n, int m)
{
std::array<int,10> count={0};
for(int unit=1; n<m; n/=10,m/=10,unit*=10) {
// count last digits
count_last_digits(n, m, count, unit);
// increment n to the next multiple of 10, but not above m
if(int inc = std::min(10-(n%10), m-n)) {
count_digits(n/10, count, unit*inc);
n += inc;
}
// decrement m to the previous multiple of 10, but not below n
if(int dec = std::min(m%10, m-n)) {
count_digits(m/10, count, unit*dec);
m -= dec; // not really necessary
}
}
return count;
}
函数count_last_digits()
和count_digits()
分别具有复杂度O(1)
和O(ln(x))
。两者都被称为O(ln(m))
次,因此后者主导了整体复杂性,这是O(ln(m)^2)
.
注意这些函数假定0 < n <= m
,即 不允许n<=0
。