爱学习的站长www.mmic.net.cn

www.mmic.net.cn 欢迎学习共同成长
公告信息
www.mmic.net.cn 欢迎学习共同成长
文章分类
文章档案
文章
O(N)的时间复杂度找出a[N]中那个重复的数字方法
2011/8/7 2:04:54

数组 a[N],存放了 1 至 N-1 个数,其中某个数重复一次。写一个函数,找出被重复的数
 

字  .时间复杂度必须为 o(N)函数原型:

方法一:

#include<iostream>
using namespace std;
int main()
{
 int a[]={1,2,3,4,5,6,8,7,8};
 int n=sizeof(a)/sizeof(int);
 int j=n-1;
 for(int i=0;i<n&&j>i;)
 {
  if(a[i]!=a[j])
  {
   j--;
   if(j==i+1)
   {
    i+=1;
    j=n-1;
   
   }
  }
  if(a[i]==a[j])
  {
   cout<<"位置在:"<<i<<"值为为:"<<a[i]<<endl;
   break;
  }

 }
 return 0;
}

方法二:利用数组的数字喝减去不重复数字的和就为重复数字ic买卖

#include<iostream>
using namespace std;
int main()
{
 int a[]={1,2,3,4,5,6,8,7,8};
 int n=sizeof(a)/sizeof(int);
 int sum1=0,sum2=0;
 for(int i=0;i<n;i++)
 {
  sum1+=a[i];
 }
 sum2=n-1+(n-1)*(n-2)/2;
 cout<<(sum1-sum2)<<endl;

 return 0;
}

 

新浪微博粉丝精灵,刷粉丝、刷评论、刷转发、企业商家微博营销必备工具"
 技术   浏览(1929)   评论(0)   关键字
  
Copyright © 2010-2020 power by CYQ.Blog - 秋色园 v2.0 All Rights Reserved