C++ 分治法统计数组中某js 数组元素出现次数的次数

来源：蜘蛛抓取(WebSpider) 时间：2015-12-13 16:12 标签： js统计数组元素个数
《数据结构、算法与应用(C++语言描述)》习题参考答案doc_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
《数据结构、算法与应用(C++语言描述)》习题参考答案doc
上传于||文档简介
&&南​开​大​学​数​据​结​构​与​算​法​ ​习​题​与​答​案
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩29页未读，继续阅读
你可能喜欢共有 1477 人关注过本帖
标题：统计数组中每个元素出现的个数，时间复杂度 O(n),空间 O(1)
来　自：西安
等　级：论坛游民
帖　子：45
专家分：32
结帖率：50%
&&已结贴√
&&问题点数：10&&回复次数：4&&&
统计数组中每个元素出现的个数，时间复杂度 O(n),空间 O(1)
下面的我完全看不懂呀不知道原理是什么求各位指教呀
一个长度大小为n的数组，数组中的每个元素的取值范围在[1,n]，且为正整数。
问：如何在时间复杂度为O(n)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。
思路：数组按序扫描，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为下标从0开始的，故输出时需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的频率。
若当前元素小于0，
&&&&&则跳过；
若当前元素大于0，
&&&&&&&&则判断其作为下标索引到的元素是否大于0，
&&&&&&&&&&&&&&& 若大于0，则索引到的元素赋值给当前元素，索引到的元素置为-1；
&&&&&&&&&&&&&&& 若小于0，则索引到的元素自减1，当前元素置为0；
#include &iostream&
void work(int a[], int n)
&&& int i = 0;
&&& while(i & n)
&&&&&&&&int temp = a[i] - 1;
&&&&&&&&if(temp & 0)
&&&&&&&&&&&&i++;
&&&&&&&&&&&&
&&&&&&&&if(a[temp] & 0)
&&&&&&&&&&&&a[i] = a[temp];
&&&&&&&&&&&&a[temp] = -1;
&&&&&&&&else
&&&&&&&&&&&&a[temp]--;
&&&&&&&&&&&&a[i] = 0;
int main()
&&& int n = 10;
&&&&&&&&int *a = new int[n];
&&&&&&&&for(int i = 0; i & i++)
&&&&&&&&&&&&cin && a[i];
&&&&&&&&work(a, n);
&&&&&&&&for(int i = 0; i & i++)
&&&&&&&&&&&&if(a[i] & 0)
&&&&&&&&&&&&&&& cout && i + 1 && & & && (-a[i]) &&
&&&&&&&&cout && &********************& &&
&&&&&&&&delete[]
&&& return 0;
搜索更多相关主题的帖子:
&&&&&&&&&&
来　自：西安
等　级：论坛游民
帖　子：45
专家分：32
回复 楼主 Edwardwang03
自己顶一下 这种思路是什么呀&&看不懂&&虽然代码执行确实没问题
来　自：西安
等　级：论坛游民
帖　子：45
专家分：32
回复 2 楼 Edwardwang03
没有人吗？大家都来看看呀&&好着急呀！！！
来　自：西安
等　级：论坛游民
帖　子：45
专家分：32
回复 3 楼 Edwardwang03
怎么都没有人回答呀？？
等　级：本版版主
威　望：131
帖　子：3245
专家分：16423
&&得分:10&
用正数/负数来区分a[i]上是原来的值，还是用于计数的值
随便举个例子，比如 { 2, 5, 5, 2, 3 }
看到第一个是 2，即2有1个，所以先将这个“1”保存到a[2-1]的位置上。但a[2-1]有有效数呀，咋办？移动一下就行。
假设我不用负数，而是用中括号来表示计数，步骤依次是
{ 2, 5, 5, 2, 3 }
5, [1], 5, 2, 3
3, [1], 5, 2, [1]
5, [1], [1], 2, [1]
[0], [1], [1], 2, [2]
[0], [2], [1], [0], [2]
结果是 1有0个, 2有2个， 3有1个， 4有0个， 5有2个
版权所有，并保留所有权利。
Powered by , Processed in 0.028073 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights ReservedC++统计数组中数字出现的次数_百度知道
C++统计数组中数字出现的次数
整形数组每元素都超两位数整数编程统计该数组全部元素数字0<img class="word-replace" src="/api/getdecpic?picenc=0ad<img class="word-replace" src="/api/getdecpic?picenc=0ad.9现少
提问者采纳
#include &cstdlib& #include &iostream&
int main(int argc, char *argv[]) { int cnt1=0; int cnt2=0, cnt3=0, cnt4=0, cnt5=0, cnt6=0, cnt7=0, cnt8=0, cnt9=0, cnt0=0; int c[30]={1, 2, 3, 4, 5, 4, 3, 3, 5, 2, 6, 2, 4, 3, 5, 4, 2, 1, 7, 1}; for(int i=0;i&20;i++) { switch(c[i]){ case 1: ++cnt1;
case 2: ++cnt2;
case 3: ++cnt3;
case 4: ++cnt4;
case 5: ++cnt5;
case 6: ++cnt6;
case 7: ++cnt7;
case 8: ++cnt8;
case 9: ++cnt9;
case 0: ++cnt0;
} } cout && &1现数：& && cnt1 && cout && &2现数：& && cnt2 && cout && &3现数：& && cnt3 && cout && &4现数：& && cnt4 && cout && &5现数：& && cnt5 && cout && &6现数：& && cnt6 && cout && &7现数：& && cnt7 && cout && &8现数：& && cnt8 && cout && &9现数：& && cnt9 && cout && &0现数：& && cnt0 && system(&PAUSE&); return EXIT_SUCCESS; }
提问者评价
好好。谢谢。
其他类似问题
为您推荐：
其他3条回答
作业自做吧
int a[100];//假设为已知整型数组int b[100];//用来存储统计结果for(int i=0;i&100;i++)b[i]=0;for(i=0; i&100; i++){
b[a[i]]++;}
#include&iostream&
int main()
int data[] = {1,1,1,1,1,1,2,2,3,3,4,4,5,6,7,7,8,8,9,9,9,0}//
原本的数组
int one = 0,
three = 0,
seven = 0,
eight = 0,
int i = sizeof data/sizeof data[0];
while(i&=0)
switch(data[i--])
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁

我要回帖

更多关于 js统计数组元素个数 的文章

 

随机推荐