文档章节

魔术索引

一贱书生
 一贱书生
发布于 2016/11/22 10:12
字数 304
阅读 4
收藏 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;  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 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.面向对象编程 面向对象编程基本概念 类和对象的关系 如何定义类 成员属性(变量) 如何创建对象实例及如何访问对象属性 对象在内存中存在的形式 栈、堆、全局区、常量区和代码区的关系 成员方...

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

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

02%
07/22
0
0
PHP魔术方法学习笔记

YII2框架controller的继承关系如下: yiibasecomponents yiibasecontroller yiiwebcontroller 而components源码里面的魔术方法让人印象深刻: 魔术方法: 是指某些情况下,会自动调用的方法,称...

风清扬-深圳
2015/12/18
50
0
Laravel5.2之PHP重载(overloading)

说明:本文主要讲述PHP中重载概念,由于Laravel框架中经常使用这块知识点,并且PHP的重载概念又与其他OOP语言如JAVA中重载概念不一样,故复习并记录相关知识点。同时,作者会将开发过程中的一...

botkenni
2016/10/24
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux命令备忘录: jobs 显示Linux中的任务列表及任务状态命令

jobs命令用于显示Linux中的任务列表及任务状态,包括后台运行的任务。该命令可以显示任务号及其对应的进程号。其中,任务号是以普通用户的角度进行的,而进程号则是从系统管理员的角度来看的...

开元中国2015
44分钟前
1
0
springboot Whitelabel Error Page(Not Found)解决方案

当出现上图图的错误时注意 报错信息 There was an unexpected error (type=Not Found, status=404). Not Found代表未访问到资源 解决方案:比较访问路径和代码的路径有没有写错 正确的访问路...

斩神魂
44分钟前
1
0
记一次hbase master停止服务的原因以及恢复

在Hdfs空间不足的情况下,拒绝写入,hbase会down掉。如果hdfs空间没有清理的情况下,重新启动hbase,会报splitlog失败,原因是wal日志重写过程中会写hdfs,写不进去导致的。重启不成功。 解决...

PageYi
48分钟前
1
0
如何从平面设计转行到UI设计?

时代的变迁,科技的进步,工具的发展,薪资的差距,促使许多人转行的原因,但平面与界面两者之间有着哪些的差异呢?如果,想要转行又该具备哪些条件呢? 平面、界面设计之间的差异性 平面设计...

mo311
51分钟前
4
0
线程池整理

一般在生产环境中,我们都不会直接new一个Thread,然后再去start(),因为这么做会不断频繁的创建线程,销毁线程,过大的线程会耗尽CPU和内存资源,大量的垃圾回收,也会给GC带来压力,延长GC停顿时间...

算法之名
52分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部