文档章节

魔术索引

一贱书生
 一贱书生
发布于 2016/11/22 10:12
字数 304
阅读 4
收藏 0
点赞 0
评论 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
博文 722
码字总数 600072
作品 0
python中类的魔术方法

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

RickyHuL ⋅ 2017/07/30 ⋅ 0

PHP 学习必备技能(基础略过)

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

风雪中的舞者 ⋅ 2015/08/05 ⋅ 0

PHP魔术方法学习笔记

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

风清扬-深圳 ⋅ 2015/12/18 ⋅ 0

Laravel5.2之PHP重载(overloading)

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

botkenni ⋅ 2016/10/24 ⋅ 0

PHP中用下划线开头的变量含义

命名的规则 加一个为私有的 加两个一般都是系统默认的,系统预定义的,即所谓: “魔术方法”与“魔术常量” PHP起止为双下划线的常量即为“魔术常量”: LINE文件中的当前行号。 FILE文件的...

linuxjd ⋅ 2014/09/13 ⋅ 1

用C语言玩转魔方阵

奇数魔方阵 奇数魔方阵就是将数字排列在nxn(n为奇数)的方阵上,要求满足各行、各列与各对角线的和相同。如下图所示,是n=5的奇数魔方阵。 填魔方阵的方法以奇数魔方阵最为简单,第一个数字...

小辰GG ⋅ 2017/11/30 ⋅ 0

PHP V5.3 中的新特性,第 1 部分: 对象接口的变化

PHP V5 和面向对象编程 与 PHP V4 提供的特性相比,2004 年发布的 PHP V5 在面向对象编程(OOP)和设计方面向前迈出了很大的一步。它提供了一些必要的改进,例如类可见性、合适的构造函数和解...

未来十年 ⋅ 2011/12/19 ⋅ 0

php中的魔术方法

魔术方法是以两个下划线""开头、具有特殊作用的一些方法,可以看做php的"语法糖"。 语法糖指那些没有给计算机语言添加新功能,而只是对人类来说更"甜蜜"的语法。语法糖往往给程序员提供了更实...

rin9958 ⋅ 2016/03/27 ⋅ 1

初探反序列化与POP CHAIN

0x00 背景 最近都在写反序列化漏洞的知识,本着循序渐进的过程,本篇研究到了反序列化与POP CHAIN相关的知识。在探索这方面知识的过程中,请教了师傅们获得了这方面的相关案例和文章,有些文...

漏斗社区 ⋅ 2017/11/21 ⋅ 0

PHP魔术方法 魔术常量(变量) 超全局变量

魔术方法 FILEDIRLINECLASSFUNCTIONMETHOD 魔术方法 construct()destory()clone() //复制对象时触发call() //当方法不存在是调用toString() //输出对象时调用set() //在类外部定义属性时触发...

大灰狼wow ⋅ 2014/05/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JPA入门,配置文件的设置

<?xml version="1.0" encoding="UTF-8"?> <persistence xmlns="http://java.sun.com/xml/ns/persistence" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http......

码农屌丝 ⋅ 11分钟前 ⋅ 0

Java基础——面向对象和构造器

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 静态成员介绍 为什么要有静态成员?静态成员用来...

凯哥学堂 ⋅ 13分钟前 ⋅ 0

vmware中Centos 7 linux的LVM磁盘扩容

系统是RHEL7(centos7差不多一样) 关闭系统,在vmware、设置、硬盘、扩展、输入数字大于当前系统内存、点击扩展。 开机再查看磁盘信息 fdisk -l 注意:可以看出sda磁盘增加了,但是根目录还...

gugudu ⋅ 23分钟前 ⋅ 0

JAVA线程sleep和wait方法区别

昨天面试,突然被问到sleep 和 wait的区别,一下子有点蒙,在这里记一下,以示警戒。 首先说sleep,sleep就是正在执行的线程主动让出cpu,cpu去执行其他线程,在sleep指定的时间过去后,cpu...

徐玉强 ⋅ 25分钟前 ⋅ 0

vuex学习--模块

随着项目复杂性增加,共享状态也越来越多。需要对转态操作进行分组,分组后在进行分组编写。学习一下module:状态管理器的模块组操作。 首先是声明: const moduleA={ state,mutations,g...

大美琴 ⋅ 27分钟前 ⋅ 0

Selenium 简单入门

安装 pip install selenium 驱动下载 https://chromedriver.storage.googleapis.com/index.html 下载最新的驱动,放入path中,可以放入Python的scripts目录下,也可以放入Chrome安装目录,并...

阿豪boy ⋅ 29分钟前 ⋅ 0

292. Nim Game - LeetCode

Question 292. Nim Game Solution 思路:试着列举一下,就能发现一个n只要不是4的倍数,就能赢。 n 是否能赢1 true2 true3 true4 false 不论删除几,对方都能一把赢5 t...

yysue ⋅ 59分钟前 ⋅ 0

6.5 zip压缩工具 6.6 tar打包 6.7 打包并压缩

zip压缩工具 zip命令可以压缩目录和文件,-r 压缩目录。 zip使用方法 zip 1.txt.zip 1.txt //压缩文件 zip -r 123.zip 123/ //压缩目录 unzip 1.txt.zip //解压 unzip 123.zip -d /root/456...

Linux_老吴 ⋅ 今天 ⋅ 0

react-loadable使用跳坑

官方给react-loadable的定义是: A higher order component for loading components with dynamic imports. 动态路由示例 withLoadable.js import React from 'react'import Loadable fro......

pengqinmm ⋅ 今天 ⋅ 0

记录工作中遇到的坑

1、ios safari浏览器向下滚动会触发window resize事件

端木遗风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部