32.【C语⾔】输⼊⼀个整数，判断各个位数之间是否存在重复数字（Demo）问题描述
输⼊⼀个整数，判断各个位数之间是否存在重复数字。因为超过⼗位数，就必然有重复数字出现，所以只研究不超过⼗位数的整数。
例如，输⼊28775，有重复数字；输⼊2875，⽆重复数字。
算法思想
1.常规算法思想
很容易会想到将每⼀位的数字放⼊数组，在放⼊该位的数字后，就与前⾯已经存⼊的数字逐个⽐对。⽐如得到某⼀位的数字放⼊arr[i]中，那么arr[i]就和arr[0]~arr[i-1]逐个进⾏⽐对，若相同，则⽴即打印结果，若不同，则循环向后执⾏，直到不断取模的数字为0时，循环结束。此时可以确定⽆重复数字。
int check_num01(num)
{
int arr[10];//num不可能超过10位，⼀旦超过10位，必然有重复数字，研究10位数以内
int len =sizeof(arr)/sizeof(arr[0]);
for(int i =0; num && i < len; i++)
{
arr[i]= num %10;//每获取到⼀位先放⼊数组arr，再⽤arr[i]以前的数和arr[i]⽐对
for(int j =0; j < i; j++)
{
if(arr[j]== arr[i])
return0;
}
scanf输入整型数组num = num /10;
}
return1;
}
算法分析
试想查询次数最多的极端情况，将判断的数字设为num，如果num是⼀个10位数，除最⾼位外，其余位的数字均和最低位不相同。外层循环执⾏⼀次，内层循环执⾏的次数和查询次数相等。
i=0时，查询次数为0
i=1时，查询次数为1
i=2时，查询次数为2
i=3时，查询次数为3
i=4时，查询次数为4
i=5时，查询次数为5
i=6时，查询次数为6
i=7时，查询次数为7
i=8时，查询次数为8
i=9时，查询次数为9
共计45次
2.借⽤哈希查的算法思想
⽤True（值为1）标记为已访问，False（值为0）标记为未访问。定义⼀个⼤⼩为10的整型数组arr，初始化为全0，即数组中的每个元素都是未被访问的。num不断除10取模得到的结果每次都放⼊index中，index起下标的作⽤。如果每次得到index对应的元素值为False，则证明还未出现重复位数，此时将该元素值设为True，即已访问的状态。下次如果得到的index是这个空间的下标，则证明出现重复位数，⽴即跳出循环，返回对应的结果。这个算法执⾏的查询次数在最坏的情况下最多为10。
int check_num02(num)
{
int arr[10]={0};//相当于数组中的元素全标记为False
int index;//⽤于存放下标
while(num >0)
{
index = num %10;//取模作为下标值
if(arr[index])//下标index对应的元素被访问过
return0;
arr[index]= True;//下标index对应的元素未被访问过，标记为访问  num /=10;
}
return1;
}
案例运⾏效果
完整代码如下
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
enum flag{False,True};//True表⽰访问，False表⽰未访问
int check_num01(num)
{
int arr[10];//num不可能超过10位，⼀旦超过10位，必然有重复数字，研究10位数以内int len =sizeof(arr)/sizeof(arr[0]);
for(int i =0; num && i < len; i++)
{
arr[i]= num %10;//每获取到⼀位先放⼊数组arr，再⽤arr[i]以前的数和arr[i]⽐对
for(int j =0; j < i; j++)
{
if(arr[j]== arr[i])
return0;
}
num = num /10;
}
return1;
}
int check_num02(num)
{
int arr[10]={0};//相当于数组中的元素全标记为False
int index;//⽤于存放下标
while(num >0)
{
index = num %10;//取模作为下标值
if(arr[index])//下标index对应的元素被访问过
return0;
arr[index]= True;//下标index对应的元素未被访问过，标记为访问
num /=10;
}
return1;
}
int main(void)
{
int num;
scanf("%d",&num);
//int ret=check_num01(num);
int ret =check_num02(num);
if(ret)
printf("unrepeated digit\n");
else
printf("repeated digit\n");
system("pause");
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。