给定一个整数51234（例如），我们需要对其数字进行排序，输出将为12345。
如何在不使用数组的情况下实现？
9个回答
30
你可以使用循环和
伪代码如下：
% 10 来提取每个数字。可以使用从0到9的外部循环来测试数字是否存在。如果存在，则打印它。伪代码如下：
n = integer // 51234
FOR digit = 0 TO 9
temp = n
REPEAT
IF temp % 10 = digit THEN PRINT digit
temp /= 10
UNTIL temp = 0
编辑：这个在gcc中的测试展示了它如何处理零和重复数字：
$ cat sortdigits.c
#include <stdio.h>
main () {
int n,digit,temp;
n = 43042025;
for (digit=0;digit<9;digit++)
for (temp=n;temp>0;temp/=10)
if (temp%10==digit) printf("%d",digit);
printf("\n");
}
$ ./sortdigits
00223445
- Carlos Gutiérrez
5
+1 我会接受这个 :) 伪代码不是必需的 :) - whacko__Cracko
美丽...嗯...在某种程度上。 - Pascal Cuoq
@Pascal：我猜。如果你想要迭代10次而不是1次数字。虽然这样可以节省内存 :-). - Alok Singhal
我认为这个方法不能处理数字中有重复数字的情况。比如说对于数字3221，它会输出123，但实际应该是1223。 - Adam Badura
@Adam 有趣的是，这也是我的第一反应。让我真正爱上这个程序的原因是当我意识到它能够工作时的那个“啊哈”时刻。 - Pascal Cuoq
7
// Bubblesort
long sortNum(long n) {
while (true) {
long a = n % 10, p = 9;
bool s = false;
for (long r = n / 10; r; r/= 10) {
long b = r % 10;
if (a < b) {
n -= p * (b - a);
s = true;
} else a = b;
p *= 10;
}
if (!s) return n;
}
}
#include <iostream>
int main(int argc, char **argv) {
if (argc > 1) {
long n = strtol(argv[1], 0, 0);
std::cout << "Unsorted: " << n << std::endl;
n = sortNum(n);
std::cout << "Sorted: " << n << std::endl;
}
return 0;
}
$ g++ -Wall -Wextra bubble-int.cpp && ./a.exe 183974425
Unsorted: 183974425
Sorted: 123445789
- Dan
3
聪明 - 直到我看到另一个答案中Steve Jessop的评论，我才仔细查看它。它需要添加一些内容来处理零。仍然非常聪明。 - Michael Burr
感谢。这有点像是一个“诡计答案”回应一个诡计问题。如果面试中有人真的给我这个答案，我会问他，“为什么这么复杂？为什么不用 std::map？”拥有能够做到这种事情的人很好，但也要知道何时最好不要这样做。 - Dan
很好。避免了字符串转换（人们通常建议对数字进行排序的正常方法），并且具有已排序数字可供进一步使用的优点。 - Tony
5
您不需要编写程序，只需使用shell命令即可实现：
echo "51234" | sed 's+\(.\)+\1\n+g' | sort | tr -d '\n'
- user231967
1
50年前，这被认为是高级编程。 :-) - Ken
4
简单：
#include <stdio.h>
#include <stdlib.h>
static void pput(int n, int c)
{
int i;
for (i=0; i < n; ++i) putchar(c);
}
int main(int argc, char *argv[])
{
int zeros = 0;
int ones = 0;
int twos = 0;
int threes = 0;
int fours = 0;
int fives = 0;
int sixes = 0;
int sevens = 0;
int eights = 0;
int nines = 0;
long num = 0;
if (argc > 1) {
char *eptr;
num = strtol(argv[1], &eptr, 0);
if (*eptr) {
fprintf(stderr, "Invalid number: '%s', using 0.\n", argv[1]);
num = 0;
}
}
do {
switch (num % 10) {
case 0: ++zeros;
break;
case 1: ++ones;
break;
case 2: ++twos;
break;
case 3: ++threes;
break;
case 4: ++fours;
break;
case 5: ++fives;
break;
case 6: ++sixes;
break;
case 7: ++sevens;
break;
case 8: ++eights;
break;
case 9: ++nines;
break;
default:
break;
}
} while ((num /= 10));
pput(zeros, '0');
pput(ones, '1');
pput(twos, '2');
pput(threes, '3');
pput(fours, '4');
pput(fives, '5');
pput(sixes, '6');
pput(sevens, '7');
pput(eights, '8');
pput(nines, '9');
putchar('\n');
return 0;
}
编译和运行：
$ gcc -Wextra -Wall -ansi -pedantic -Wfloat-equal -Wundef -Wshadow \
-Wpointer-arith -Wcast-qual -Wcast-align -Wstrict-prototypes \
-Wswitch-default -Wswitch-enum -Wstrict-overflow=5 \
-Wdeclaration-after-statement -Wwrite-strings -Wconversion \
-Waggregate-return -Wunreachable-code a.c
$ ./a.out
0
$ ./a.out 54321
12345
$ ./a.out 9834346
3344689
$ ./a.out hello
Invalid number: 'hello', using 0.
0
另一种解决方案，不使用数组，代码行数也很短：
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
int main(int argc, char *argv[])
{
long num = 0;
int i;
size_t *freq;
if (argc > 1) {
char *eptr;
num = strtol(argv[1], &eptr, 0);
if (*eptr || errno == ERANGE) {
fprintf(stderr, "Invalid number: '%s', using 0.\n", argv[1]);
num = 0;
}
}
if ((freq = calloc(10, sizeof *freq)) == NULL) {
perror("malloc failure");
return EXIT_FAILURE;
}
do
++freq[num % 10];
while ((num /= 10));
for (i=0; i < 10; ++i) {
size_t j;
for (j=0; j < freq[i]; ++j)
putchar(i + '0');
}
putchar('\n');
free(freq);
return EXIT_SUCCESS;
}
是的，我知道“正确”的解决方案。但是为什么不使用数组来解决这个问题呢？正如其中一位评论者所说的那样，在C语言中如果公司不能让我使用数组，我是不想为这样的公司工作的。
- Alok Singhal
20
2这有多简单啊？！！所有那些代码行都是必要的吗？：O - whacko__Cracko
使用数组会使得它如此简单，即使一个孩子也能做到！:P - whacko__Cracko
1@nthgreek：我知道这个要求是为了让它不容易。但是有很多非常好的、不容易的问题可以供面试官提问。 - Alok Singhal
@kriss：谢谢。我不明白这个问题的意义所在。不使用数组并不能证明你有什么真正的技能。 - Alok Singhal
@Steve：我看到的问题是，虽然“挽起袖子直接解决问题”是很好的态度，但如果你的数组有问题，这里不是处理它的地方。我想要的候选人会说（就像我可能会说的）：“给我你的C编译器的源代码，我会修复它（显然）有问题的数组实现”。我不希望有同事在某个层面上发现了一个bug，却没有想到去修复它，而是选择在系统的其他每个层面绕过它——比如对int的数字进行冒泡排序。我曾经不得不维护过这些人写的代码，那并不好玩。 - Ken
显示剩余15条评论
4
总体概述：
- 循环 i 从 0 到 9
- 在每一个循环迭代中，通过另一个循环遍历数字中的每个位数（使用“mod 10”操作剥离数字的位数，直到数字剩下零） - 如果它与当前正在处理的数字匹配，则打印出来
唯一可能棘手的部分可能是正确地处理零 - 您不想要太多零，并且您将要正确处理输入为零的边缘情况。
实际实现作为一项练习留给读者完成...
- Michael Burr
3
在循环中将整数除以10。在每次迭代中打印余数。
这里的“sort”是什么意思？要进行真正的排序，您需要两个循环。其中一个循环将从0到9。另一个循环是早期描述过的。
int main()
{
int x = 0;
cin >> x;
for ( int l = 0; l < 10; ++l )
{
int rem = x % 10;
int tx = x / 10;
while ( rem || tx )
{
if ( rem == l ) cout << rem;
rem = tx % 10;
tx = tx / 10;
}
}
cout << endl;
}
- Kirill V. Lyadvinsky
1
确实，数组已经过时了，但我们有更好的容器：
void foo(unsigned i) {
std::set<char> digits;
do {
digits.insert(`0` + i % 10);
i /= 10;
while(i!=0);
}
如果您的输入包含像887这样应该打印为788的数字，请使用multiset
- MSalters
1
我认为如果不允许使用数组，那么事实上任何容器都不允许使用。 - Adam Badura
0
可以尝试类似于插入排序的算法。基本上，每次从旧数中取一个数字，并将其放入正确的位置，再创建一个新的数字。就像这样。
while(num!=0){
dig = num%10; // get the last digit
if(newNum=0 ) newNum+=dig;
else{
newNumTemp = 0; flag =1;i =1;
while (newNum != 0){
Newdig = newNum%10;
if(flag){
if (Newdig >= dig )
{NewNumTemp = Newdig*(10^i)+ NewNumTemp; }
else { flag=0; NewNumTemp = dig*(10^i) +NewNumTemp; i++;NewNumTemp = Newdig* (10^i)+ NewNumTemp;}
} // end of outer if
i++;
newNum/=10;
} // end of while
newNum= newNumTemp;
}// end of else
num/=10;
}// end of outer while
- Aman Neelappa
1
任何以四个空格开头的行都不会被修改。单击编辑框右上角的“？”获取帮助。 - Alok Singhal
0
创建一个容器接口，类似于 vector，其中运算符引用第 i 个十进制数字。您还需要定义迭代器和其他内容。
然后在其上调用 std::sort。;)
- e.tadeu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接