注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(74)-多出的数字[算法]  

2018-03-21 15:10:41|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题:在两个输入的数组中除了一个数字之外其余数字的值和顺序都相同,第一个数组比第二个数组多一个数字。请问如何找出第一个数组中多出的数字的下标?例如如果输入两个数组{2, 4, 6, 8, 9, 10, 12}{2, 4, 6, 8, 10, 12},则输出4,该下标对应的数字是9。

 

分析:很多应聘者在面试的时候遇到这个问题都能想到最直观的解法。我们可以分别从两个数组的第一个数字开始逐一扫描,直到遇到的两个数组中对应数字不相等的下标,就是符合要求的输出。例如在数组{2, 4, 6, 8, 9, 10, 12}{2, 4, 6, 8, 10, 12}中,下标为0的两个数字都是2,下标为1的两个数字都是4。这样逐个扫描两个数组直到下标为4时,第一个数组中对应的数字是9,而第二个数组中多出的数字是10。数字9正好是第一个数组中多出的数字。

 

由于这个解法可能逐一扫描数组中的每个数字,因此对长度为n的数组而言它的时间复杂度是O(n)

 

如果想实现比顺序查找更快速地在数组中查找某个数字,通常我们需要应用二分查找。我们可以先尝试比较两个数组中间的数字是否相同。如果中间的两个数字相同,则两个数组左边的数字都相同,接下来我们我们只需要在两个数组的右边查找。如果中间的两个数字不相同,我们则比较在它们前面的两个数字是否相同。如果前面两个也不同,说明多出的数字在左边,下次我们只需要在左边的子数组中查找。如果前面两个数字相同,则第一个数组的中间的数字就是多出来的数字。

 

还是以数组{2, 4, 6, 8, 9, 10, 12}{2, 4, 6, 8, 10, 12}为例。由于第一个数组的长度为7,它的中间坐标为3(因为(0+6)/2=3)。由于两个数组中下标为3的两个数字都是8,这说明两个数组左半边都是相同的,接下来只需要查找数组的右边半个子数组即可。第一个数组的右边半个子数组为{9, 10, 12}。该子数组的中间下标为5(因为(4+6)/2=5),对应的数字是10。但在第二个数组中下表为5的数字是12,它们不相同。在两个数组中它们前面的数字分别是910,也不相同,因此我们接着查找该子数组的左边半个子数组,即子数组{9},它只包含一个下标为4的数字。我们注意到第二个数组中下标为4的数字是10,不相等。但是它们前面的两个数字都是8,是相同的。因此数字9就是第一个数组中多出的数字。

 

下面的Java代码实现了上述算法:

public static int findExtra(int[] array1, int[] array2) {

    if (array1 == null || array2 == null

            || array1.length != array2.length + 1) {

        return -1;

    }

 

    int start = 0;

    int end = array1.length - 1;

    while (start <= end) {

        int mid = start + (end - start) / 2;

        if (mid == array1.length - 1) {

            return mid;

        }

 

        if (array1[mid] != array2[mid]) {

            if (mid == 0 || array1[mid - 1] == array2[mid - 1]) {

                return mid;

            }

 

            end = mid - 1;

        } else {

            start = mid + 1;

        }

    }

 

    return -1;

}


代码中有两个细节值得注意。如果当我们下标mid0时两个数组中对应的数字仍然不相同,则第一个数组中的第一个数字(下表为0)就是多出的数字。另外,当下标mid指向第一个数组的最后一个数字时我们不能试图去得到第二个数组中下标为mid的数字。因为第二个数组比第一个数组少一个数字,此时下标mid已经超出了第二个数组的边界。代码执行到这一步说明前面的数字都相等,那么第一个数组中的最后一个数组就是多出的数字,不用比较就可直接返回。

 

第二种解法应用了二分查找的思想,因此时间复杂度为O(logn),比第一种直观的解法效率要高。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(404)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018