文档章节

魔术索引

一贱书生
 一贱书生
发布于 2016/11/22 10:12
字数 304
阅读 38
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

/**
 * 功能:在数组A[0…n-1]中,有所谓的魔术索引,满足条件A[i]=i。
 * 给定一个有序整数数组,元素值各不相同,找出一个魔术索引。
 * 
 * 进阶:如果数组元素有重复值,如何处理

 */

两种方法:

方法一:

 

[java] view plain copy

 

  1. //穷举法  
  2. public static int getMagicIndex(int[] array){  
  3.     for(int i=0;i<array.length;i++){  
  4.         if(array[i]==i)  
  5.             return i;  
  6.     }  
  7.     return -1;  
  8. }  


方法二:

 

 

[java] view plain copy

 

  1. //二分查找法  
  2. /** 
  3.  * 思路:利用数组有序的特点,运用模式匹配法。 
  4.  * @param array 
  5.  * @return 
  6.  */  
  7. public static int getMagicIndex2(int[] array){  
  8.     return judge(array,0,array.length-1);  
  9. }  
  10.   
  11. public static int judge(int[] array,int start,int end){  
  12.     if(end<start||start<0||end>array.length)  
  13.         return -1;  
  14.       
  15.     int mid=(start+end)/2;  
  16.     if(array[mid]==mid)  
  17.         return mid;  
  18.     else if(array[mid]<mid)  
  19.         return judge(array,mid+1,end);  
  20.     else   
  21.         return judge(array,start,mid-1);          
  22. }  


 

 

进阶:

 

[java] view plain copy

 

  1. //进阶:如果数组元素有重复值  
  2. public static int getMagicIndex3(int[] array){  
  3.     return judge2(array,0,array.length-1);  
  4. }  
  5.   
  6. public static int judge2(int[] array,int start,int end){  
  7.     if(end<start||start<0||end>array.length)  
  8.         return -1;  
  9.       
  10.     int midIndex=(start+end)/2;  
  11.     int midValue=array[midIndex];  
  12.     if(midIndex==midValue)  
  13.         return midIndex;  
  14.   
  15.     //搜索左半部分   
  16.     int leftIndex=Math.min(midIndex-1, midValue);  
  17.     int left=judge2(array,start,leftIndex);  
  18.     if(left>=0)  
  19.         return left;  
  20.       
  21.     //搜索右半部分  
  22.     int rightIndex=Math.max(midIndex+1, midValue);  
  23.     int right=judge2(array,rightIndex,end);  
  24.       
  25.     return right;  

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中

评论(0)

python中类的魔术方法

目的:学习python中class的magic methods,提高编程效率。 环境:ubuntu 16.4 python 3.5.2 在学习class时一定会接触到它的magic methods,比如常用init,形式都是前后有双下划线。除了这个必...

RickyHuL
2017/07/30
0
0
php面向对象高级-魔术方法与迭代器

1,魔术方法set与get, call >这些魔术方法,将在相关的属性或者方法不存在时调用 >函数原型   .function set( $property, $value ):传递属性的名字和新的值   .function get( $propert...

osc_q4og6y57
2018/02/22
0
0
流畅的Python---纸牌(魔术方法:__getitem__ 与 __len__ )

常用Python的内建模块(collections)、魔术方法(getitem 与 len )构建纸牌   1.常用内建模块 collections、base64、struct、hashlib、itertools、XML、HTMLParser     collections...

osc_c438keit
2019/04/09
2
0
PHP 学习必备技能(基础略过)

1.面向对象编程 面向对象编程基本概念 类和对象的关系 如何定义类 成员属性(变量) 如何创建对象实例及如何访问对象属性 对象在内存中存在的形式 栈、堆、全局区、常量区和代码区的关系 成员方...

风雪中的舞者
2015/08/05
109
0
日常 Python 编程优雅之道

3 个可以使你的 Python 代码更优雅、可读、直观和易于维护的工具。 Python 提供了一组独特的工具和语言特性来使你的代码更加优雅、可读和直观。为正确的问题选择合适的工具,你的代码将更易于...

02%
2018/07/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Python--报错RecursionError: maximum recursion depth exceeded in comparison

Python--报错RecursionError: maximum recursion depth exceeded in comparison 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本...

归子莫
41分钟前
21
0
聊聊SpinalTap的BinlogEventListener

序 本文主要研究一下SpinalTap的BinlogEventListener BinlogEventListener SpinalTap/spinaltap-mysql/src/main/java/com/airbnb/spinaltap/mysql/binlog_connector/BinaryLogConnectorSourc......

go4it
58分钟前
29
0
Spring的扩展原理

MainConfigOfExt.class /** * 扩展原理: * 1. BeanPostProcessor:bean后置处理器;bean创建对象初始化前后进行拦截工作 * BeanFactoryPostProcessor:beanFactory的后置处理器 * ...

与你同行7
今天
37
0
C# 基础知识系列- 16 开发工具篇

0. 前言 这是C# 基础知识系列的最后一个内容讲解篇,下一篇是基础知识-实战篇。这一篇主要讲解一下C#程序的结构和主要编程工具。 1. 工具 工欲善其事必先利其器,在实际动手之前我们先来看看...

月影南溪
今天
15
0
阿里双11超级工程:PB级文件分发重器蜻蜓

有图有介绍见: http://tech.it168.com/a2017/1114/3179/000003179630.shtml 蜻蜓开源地址:https://github.com/alibaba/dragonfly 2017天猫双11, 交易峰值32.5万/秒,支付峰值25.6万/秒,数...

whoisliang
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部