文档章节

魔术索引

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

没有更多内容

加载失败,请刷新页面

加载更多

二十分钟教你如何将区块链应用与函数计算相结合

前言 本篇文章适合对区块链应用感兴趣或是想要通过函数计算服务进一步开发区块链应用的新人。本文将结合阿里云区块链服务、阿里云函数计算服务、阿里云日志服务 以及社区应用 Marbles,手把手...

阿里云官方博客
4分钟前
0
0
Double数相加后结果不准确

在我们进行两个double运算时,例如:2..0-1.1 不是想象的输出0.9,而是0.89999999999999999。其主要原因是浮点数值采用二进制系统表示,而在二进制系统中无法精确的表示分数1/10。这就好像十...

嘴角轻扬30
11分钟前
0
0
去除移动端点击效果

移动端点击时,会有一个类似active的短暂背景淡出效果,去除该效果可使用 -webkit-tap-highlight-color: rgba(255, 0, 0, 0);

originDu
13分钟前
0
0
腾讯云与MariaDB 基金会签署战略合作,共建全球开源生态圈

本文由云+社区发表 腾讯云日前与MariaDB基金会正式签署战略合作协议,2019年,腾讯云将继续以白金会员身份为基金会的发展提供强有力的资源支持,与MariaDB全球用户和开发者一道,共建开放共赢...

腾讯云加社区
18分钟前
1
0
Kotlin的SAM(Single Abstract Method)

今天有人在群里问kotlin支持SAM的问题,其实kotlin不支持SAM,因为人家支持FP(function programing) package reactinterface Test { fun print()}class TestInterface(var...

SuShine
19分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部