文档章节

魔术索引

一贱书生
 一贱书生
发布于 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

获取多个集合列表的笛卡尔积

获取多个集合笛卡尔积 电商中典型业务场景:商品搜索 单属性属性值之间为并查询 不同属性的属性值之间查询为与查询 import java.util.ArrayList;import java.util.List;/** * Created w...

键走偏锋
23分钟前
0
0
echarts 迁移地图 控制鼠标缩放大小比例

在网上找了好久没有找到解决方式,还是重新看了一下文档,终于找到的解决方案, zoom:1, //默认显示级别 scaleLimit:{min:1,max:3}, // 缩放级别 echarts 文档-配置项链接 http://echarts.b...

心驰
27分钟前
0
0
Boot2Docker ISO is out-of-date,

Boot2Docker ISO is out-of-date, downloading the latest release. 使用docker-machine时无法更新Boot2Docker ISO导致创建vm machine失败 解决方法:关闭网络,创建好之后再开启...

writeademo
35分钟前
0
0
在 Tomcat 中设置 Tapestry 框架的 html 热加载

如果开发中使用到了 Tapestry 这个框架,如果事先没有设置过的话,开发的时候 html 是不会热加载的,也就是说修改了 html 文件,不能刷新浏览器后立马看到修改完的效果,必须先重新启动应用服...

LeoXu
57分钟前
0
0
【微服务】开启巨石应用到微服务的探索

背景 在过去的一年时间里,我一直在从事一件事情,将现有的单体应用(巨石应用)向微服务改造。 接下来,将持续整理一些在微服务路上的学习与成长。 为什么要做微服务 单体应用,开发、部署简...

艳沐石
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部