黑马程序员技术交流社区
标题:
设计一个算法找 出这个数字.说明:每个元素只能被访问一次
[打印本页]
作者:
铿锵科技
时间:
2013-8-7 21:07
标题:
设计一个算法找 出这个数字.说明:每个元素只能被访问一次
本帖最后由 铿锵科技 于 2013-8-10 23:22 编辑
有一个1001个元素的数组a[n],每个元素都在1到1000这些整数中取值,其
中只有一个数得复,并且数组中每个元素只能被访问一次,设计一个算法找
出这个数字.说明:每个元素只能被访问一次,就像执行int v=a[1],v变量
和a[1]元素不能再访问.求高手指教
作者:
夜空闪亮
时间:
2013-8-7 22:20
问题问的不清楚啊，“只有一个数得复”是什么意思啊？
作者:
breaveheart
时间:
2013-8-8 09:49
我的想法是：
作者:
breaveheart
时间:
2013-8-8 09:53
不好意思打快了不小心发表了。。。。
我原来的想法是既然1-1000这1000个数肯定存在，
那么可以在这个数组里找出这1000个数再找出最后一个剩下来的数的角标，
不过发现也是多次访问查找了。汗，只能同求答案- -
作者:
breaveheart
时间:
2013-8-8 10:03
只要找出这个数啊- - 昏。那我倒是有思路了。
对这个数组用角标的方式求和得num，
又因为1-1000个数肯定都出现一遍，
所以直接用num-(1+1000)*500就行了，
求得的就是重复的数。
作者:
单凯
时间:
2013-8-8 10:35
本帖最后由 单凯 于 2013-8-8 10:46 编辑
一共有1001个数，其中1000个数是从1到1000取值的（而且取完一遍），另外一个数是重复数，
那就用这1001个数的和，与前头那个1000数的等差数列相减，便得出那个重复数了.
for （int num=0,i=0;i<1001;i++）
num+=a【i】
-i;
i从0开始，所以减的是1到1000的和。
作者:
白堇翎
时间:
2013-8-8 13:30
数组==>ArrayList==>HashSet==>ArrayList.removeAll(HashSet)===>得到那个重复的数字
这样行不行?
作者:
心灵之歌
时间:
2013-8-8 13:38
public static void main(String[] args) {
int[] arr=new int[1001];//定义一个能够存储1001个元素的数组。
int sum=0;//定义一个变量用于存储arr数组元素里面的所有总和。
int sum1=0;//定义一个变量用于存储1-1000的总和。
for(int i=0;i<arr.length;i++){
sum+=arr[i];//用for循环，遍历求出集合中所有元素的总和。
}
for(int i=0;i<1001;i++){
sum1+=arr[i];//用for循环，遍历求出1-1000中所有元素的总和。
}
int a=sum-sum1;//假设a为，arr数组里面重复的元素！
System.out.println("数组里面重复的数字为："+a);
}
作者:
夜写意
时间:
2013-8-8 14:57
不可能实现吧？按照你的意思，就是一访问到这个数就知道他是不是那个重复的数了。通过比较或者转成集合，都不止访问一次。除非是通过数学的算法。那这样又不是程序的算法了。
数学的算法可以用1001个元素的和减去1到1000的和就是这个数。这个必须是有两个先决条件：1001个元素的值是从1到1000取的。而且只有一个数重复。
如果换成程序，那么可以这么来：
int sum = 0;
int sumA = 0;
int num;
for(int i=1;i<=1000;i++)
{
sum += i;
}
for(int i = 0;i<a.length;i++)
{
sumA += a[i];
}
num = sumA - sum;
复制代码
作者:
铿锵科技
时间:
2013-8-10 23:15
谢了楼上的多位辛苦了!
作者:
会飞的狼
时间:
2013-8-10 23:31
容量为1001的数组，每个位置中的数都是1——1000范围内的，只有一对是重复的，那么肯定是1——1000中每个数字都出现了一次，只有一个出现了两次，那么你对这个数组进行求和就行了int sum = 0,x=0;
for(int i:arr)
{
sum +=i;
}
循环结束后用sum减去1加到1000的和就是那个重复的数了
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2