文档章节

有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置

一贱书生
 一贱书生
发布于 2016/11/24 08:45
字数 286
阅读 13
收藏 0

版权声明:本文为博主原创文章,未经博主允许不得转载。

/**

 * 功能:有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置。

 */
[java] view plain copy

 

  1. /** 
  2.  * 思路:对二分查找法做修改,与mid比较的地方,如果mid为空字符串,则将mid换到离它最近的非空字符串的位置。 
  3.  * @param strings 
  4.  * @param str 
  5.  * @return 
  6.  */  
  7. public static int search(String[] strings,String str){  
  8.     if(strings==null||str==null||str=="")  
  9.         return -1;  
  10.     return searchStr(strings,str,0,strings.length);  
  11. }  
  12.   
  13. public static int searchStr(String[] strings,String str,int first,int last){  
  14.     if(first>last)  
  15.         return -1;  
  16.       
  17.     int mid=(first+last)/2;  
  18.     //若mid为空字符串,找出离它最近的非空字符串  
  19.     if(strings[mid].isEmpty()){  
  20.         int left=mid-1;  
  21.         int right=mid+1;  
  22.         while(true){  
  23.             if(left<first&&right>last)  
  24.                 return -1;  
  25.             else if(right<last&&!strings[right].isEmpty()){  
  26.                 mid=right;  
  27.                 break;  
  28.             }else if(left>first&&!strings[left].isEmpty()){  
  29.                 mid=left;  
  30.                 break;  
  31.             }  
  32.             left--;  
  33.             right++;  
  34.         }  
  35.     }  
  36.       
  37.     if(str.equals(strings[mid]))  
  38.         return mid;  
  39.     else if(strings[mid].compareTo(str)<0)  
  40.         return searchStr(strings, str, mid+1, last);//搜索右半边  
  41.     else  
  42.         return searchStr(strings, str, first, mid-1);//搜索左半边          
  43. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
玩转算法面试:(三)LeetCode数组类问题

数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序 查找:二分查找法 数据结构:栈;队列;堆 …… 如何写出正确的程序 建立一个基础的框架,什么是正确的程序 二分查...

天涯明月笙
2017/09/20
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
10/02
0
0
【程序猿必备】数据结构与算法精选面试题

有很多计算机科学技术专业的毕业生和程序员申请在Uber和Netflix这样的初创公司、谷歌和阿里巴巴这样的大公司以及Infosys或Luxsoft等以服务为基础的公司从事编程、编码和软件开发工作,但他们...

【方向】
10/07
0
0
算法编程题

1、 题目描述 对于一个字符串,请设计一个高效算法,找到第一次重复出现的字符。 给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符,字符串...

tomcater
2016/07/05
174
3

没有更多内容

加载失败,请刷新页面

加载更多

Prometheus + Grafana 监控 Linux 和 MySQL 安装配置

一、介绍Prometheus Prometheus(普罗米修斯)是一套开源的监控&报警&时间序列数据库的组合,起始是由SoundCloud公司开发的。随着发展,越来越多公司和组织接受采用Prometheus,社区也十分活...

PeakFang-BOK
8分钟前
0
0
缓存与数据库的双写一致性问题

数据库与缓存的双写一致性问题 cache aside pattern 数据库与缓存的双写一致性 为什么是先删除缓存再更新数据库,而不是反过来 并发读写下的一致性问题 总结: 读请求和写请求串行化,串到一个...

grace_233
14分钟前
0
0
详解java并发包源码之AQS独占方法源码分析

AQS 的实现原理 学完用 AQS 自定义一个锁以后,我们可以来看一下刚刚使用过的方法的实现。 分析源码的时候会省略一些不重要的代码。 AQS 的实现是基于一个 FIFO 队列的,每一个等待的线程被封...

小刀爱编程
18分钟前
0
0
Golang中的panic和recover

func panic(interface{})和func recover() interface{}是Golang中用于错误处理的两个函数。 panic的作用就是抛出一条错误信息,从它的参数类型可以看到它可以抛出任意类型的错误信息。在函数...

xtof
22分钟前
0
0
Mybatis Mapper.xml 配置文件中 resultMap 节点的源码解析

相关文章 Mybatis 解析配置文件的源码解析 Mybatis 类型转换源码分析 Mybatis 数据源和数据库连接池源码解析(DataSource) Mybatis Mapper 接口源码解析(binding包) Mybatis 解析 SQL 源码...

tsmyk0715
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部