三道简单算法题(二)-阿里云开发者社区

开发者社区> 长征2号> 正文

三道简单算法题(二)

简介:
+关注继续查看

1:试着用最少的比较次数去寻找数组中的最大值和最小值。

思路一:扫描数组两次,第一次等到最大值,第二次等到最小值。总共比较次数2N,这是大家都可以想到的。

思路二:定义两个变量存放最大值和最小值,将数组两两分组,两两进行比较,大的和最大值进行比较,小的和最小值比较,数组两两比较次数是N/2,分别与最大值和最小值比较的次数为N,总共比较次数1.5N。好久没写算法了,于是蛋疼得想实现一下。

复制代码
//1:试着用最少的比较次数去寻找数组中的最大值和最小值。 
void FindMaxMin(int *A,int size,int* Max,int* Min)
{ 
    int i=(size & 1)?1:0;
    *Max=*Min=A[0]; 
    for(;i<size;i=i+2)
    {
        if(A[i]>A[i+1])
        {
            if(A[i]>*Max) 
                *Max=A[i]; 
            if(A[i+1]<*Min) 
                *Min=A[i+1]; 
        }else{
            if(A[i+1]>*Max) 
                *Max=A[i+1]; 
            if(A[i]<*Min) 
                *Min=A[i]; 
        }
    }  
}

void FindMaxMinTest(){
    int A[9]={2,4,6,8,9,1,3,5,7};
    int Max=0;
    int Min=0;
    FindMaxMin(A,9,&Max,&Min);
    cout<<Max<<endl;
    cout<<Min<<endl;
}
复制代码

写完之后,发现这太简单了,不过瘾,于是又实现了两题,当然这三道题的思路都很早之前就看过。

2:给一个整数数组,求数组中重复出现次数大于数组总个数一半的数

按照抵消的思路,如果存在一个数出现的次数大于数组的一半,将这个数与其他不同的数进行一一抵消,最后剩下的必定就是这个数,然后再验证这个数是否是真的出现次数超过数组的一半,实现如下,以前也实现过,但是发现这次的实现和以前的实现出入较大,这是为什么呢?

复制代码
//2:给一个整数数组,求数组中重复出现次数大于数组总个数一半的数
int MoreThanHalf(int *A,int size)
{ 
    int num=A[0];
    int count=1;
    for(int i=1;i<size;i++)
    { 
        if(num==A[i])
        {
            count++;
        }else{
            count--;  
            if(count==0)
            { 
                num=A[i];
                count=1;
            }
        } 
    }
     
    count=0;
    for(int i=0;i<size;i++)
    {
        if(A[i]==num)
            count++;
    }  
    return count>(size/2)? num:-1;
}

void MoreThanHalfTest()
{
    int A[9]={ 1, 1,2, 1, 2, 2, 1, 2, 2 };
    cout<<MoreThanHalf( A,9);
}
复制代码

 

3:给一个很大的数组,里面有两个数只出现过一次,其他数都出现过两次,把这两个数找出来

按照异或运算的思路解题。假设这两个数分别为A,B;将数组的每个元素异或运算一次,得到这两个数的异或运算结果C,因为其他的数都是两两出现,异或运算的值为0,这个结果值C的二进制位中为1的位必只有A,B其中一个数有,因为异或运算就是不同的值才能得到1,相同的为0。即1&1=0;0&0=0;1&0=1。那么我们就可以随便从结果C中取出一个二进制位为1的位与其后面的0得到一个数,若结果C的二进制位后8位为00010100,那么我们就可以得到4(二进制100),然后将数组中的每一个与4进行异或运算,这样我们就能将数组分为两组,A,B就被分到不同的组,其他的数被分到那个组并不用管,因为经过异或运算之后的值都为0,将两组分别就行以后运算之后就能得到A,B的值了,其他的数都互相抵消了。

复制代码
//3:给一个很大的数组,里面有两个数只出现过一次,其他数都出现过两次,把这两个数找出来
void FindTwoNum(int* A,int size, int* first,int* second)
{
    int excVal=A[0];
    for(int i=1;i<size;i++)
    {
        excVal^=A[i];
    }
    int s1=1;
    int s2=excVal;
    while((s2&1)==0)
    {
        s2>>=1;
        s1<<=1;
    }
    *first=excVal;
    for(int i=0;i<size;i++)
    { 
        if(s1&A[i]) 
            *first^=A[i];
    }
    *second=excVal^*first;
}

void FindTwoNumTest()
{
    int A[12]={2,1,1,2,3,3,5,7,4,4,7,9};
    int first=0,second=0;
    FindTwoNum(A,12,&first,&second);
    cout<<first<<endl;
    cout<<second;
}
复制代码

三道简单算法题(一)



本文转自啊汉博客园博客,原文链接:http://www.cnblogs.com/hlxs/archive/2013/03/28/2986191.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9998 0
RSA与AES混合加密算法的实现
RSA与AES加密算法所产生的密钥数不一样,它们是如何进行加密的呢? 接收方生成RSA密钥对,将其中的RSA公钥传递给发送方(接收方与发送方建立连接是需要认证的,SSL/TLS协议可以确保RSA公钥的安全完整),然后用RSA公钥对AES密钥进行加密,加密后的结果传递给接收方,接收方用RSA私钥解密后,得到AES密钥,最后使用AES密钥解密,从而达到安全互通数据的目的。(如下图所示)
1569 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10880 0
RANSAC算法在图像拼接上的应用的实现
关于算法原理请参考《基于SURF特征的图像与视频拼接技术的研究》。一、问题提出         RANSAC的算法原理并不复杂,比较复杂的地方在于“建立模型”和“评价模型”。我们经常看到的是采用“直线”或者“圆”作为基本模型进行“建立”,而采用所有点到该“直线”或“圆”的欧拉距离作为标准来“评价”(当然是越小越好)。
2290 0
高德地图 AMAP-TECH 算法大赛火热进行中······
如何通过计算机视觉等人工智能算法,基于视频图像中识别到的路面信息来判断道路通行状态,提高道路路况状态判断的准确性,从而提升高德地图用户的出行体验?
751 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13793 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11879 0
Silverlight中非对称加密及数字签名RSA算法的实现
RSA算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性。
669 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7327 0
+关注
1703
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载