32.【C语言】输入一个整数，判断各个位数之间是否存在重复数字（Demo） |
您所在的位置：网站首页 › c语言输入数字输出位数 › 32.【C语言】输入一个整数，判断各个位数之间是否存在重复数字（Demo） |
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 if (arr[j] == arr[i]) return 0; } num = num / 10; } return 1; } 算法分析试想查询次数最多的极端情况，将判断的数字设为num，如果num是一个10位数，除最高位外，其余位的数字均和最低位不相同。外层循环执行一次，内层循环执行的次数和查询次数相等。 i=0时，查询次数为0i=1时，查询次数为1i=2时，查询次数为2i=3时，查询次数为3i=4时，查询次数为4i=5时，查询次数为5i=6时，查询次数为6i=7时，查询次数为7i=8时，查询次数为8i=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对应的元素被访问过 return 0; arr[index] = True; //下标index对应的元素未被访问过，标记为访问 num /= 10; } return 1; } 案例运行效果
|
【本文地址】
今日新闻 |
推荐新闻 |