文档章节

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

一贱书生
 一贱书生
发布于 2016/11/24 08:45
字数 286
阅读 5
收藏 0
点赞 0
评论 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
博文 723
码字总数 600072
作品 0
Android 面试文档分享

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

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

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

天涯明月笙
2017/09/20
0
0
算法编程题

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

tomcater
2016/07/05
174
3
javascript--数组

摘自ES6入门--阮一峰 扩展运算符(spread)是三个点()。它好比 rest 参数的逆运算,将一个数组转为用逗号分隔的参数序列。 (1)复制数组 ES5 只能用变通方法来复制数组。 扩展运算符提供了...

前端笔记
01/12
0
0
JS基础(二)-12.10

(1)JS Date(日期)的显示: 输出当下时间: var m=new Date();(其中Date的“D”必须要大写) console.log(m); (2)JS中的计时器: x.setInterval("js语句",时间)(其中时间十一毫秒...

TroubleMakerLi
2017/12/14
0
0
java split() 用法

一、参考文献 1.1 https://blog.csdn.net/daxiangzhang/article/details/2149896 1.2 java String.split()使用注意点和问题 二、用法(完全copy的参考文献1.1,用作备份,侵删) java.lang....

Clover286
04/24
0
0
玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set和map 容器类 屏蔽实现细节 了解语...

天涯明月笙
2017/09/21
0
0
String类型的属性和方法

属性   字符串String类型的每个实例都有一个length属性,表示字符串中的字符个数。由于字符串是不可变的,所以字符串的长度也不可变   字符串的length属性不会在for/in循环中枚举,也不能...

jjjssswww
2017/06/06
0
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
JAVA实用工具类

在开发java项目时,经常都需要频繁处理数据,如果能非常合适、严谨的处理数据,那么将对程序有莫大的好处,例如,提高程序的稳定性,而且有时候数据在使用前是必须处理的,否则就会出错。例如...

dmrs
2015/10/18
22
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据教程(2.11):keeperalived+nginx高可用集群搭建教程

上一章节博主为大家介绍了目前大型互联网项目的系统架构体系,相信大家应该注意到其中很重要的一块知识nginx技术,在本节博主将为大家分享nginx的相关技术以及配置过程。 一、nginx相关概念 ...

em_aaron
21分钟前
0
0
Apache Directory Studio连接Weblogic内置LDAP

OBIEE默认使用Weblogic内置LDAP管理用户及组。 要整理已存在的用户及组,此前办法是导出安全数据,文本编辑器打开认证文件,使用正则表达式获取用户及组的信息。 后来想到直接用Apache Dire...

wffger
28分钟前
2
0
HFS

FS,它是一种上传文件的软件。 专为个人用户所设计的 HTTP 档案系统 - Http File Server,如果您觉得架设 FTP Server 太麻烦,那么这个软件可以提供您更方便的档案传输系统,下载后无须安装,...

garkey
33分钟前
1
0
Java IO类库之BufferedInputStream

一、BufferedInputStream介绍 /** * A <code>BufferedInputStream</code> adds * functionality to another input stream-namely, * the ability to buffer the input and to * sup......

老韭菜
35分钟前
0
0
STM 32 窗口看门狗

http://bbs.elecfans.com/jishu_805708_1_1.html https://blog.csdn.net/a1985831055/article/details/77404131...

whoisliang
昨天
0
0
Dubbo解析(六)-服务调用

当dubbo消费方和提供方都发布和引用完成后,第四步就是消费方调用提供方。 还是以dubbo的DemoService举例 -- 提供方<dubbo:application name="demo-provider"/><dubbo:registry address="z...

青离
昨天
1
0
iptables规则备份和恢复、firewalld的9个zone以及操作和service的操作

保存以及备份iptalbes规则 设定了的防火墙规则要进行保存,否则系统重启后这些规则就没有了,使用命令 ”service iptables save ” 会把设定好的防火墙规则保存到文件/etc/sysconfig/iptabl...

黄昏残影
昨天
0
0
k8s image

k8s.gcr.io/kube-apiserver-amd64:v1.11.0k8s.gcr.io/kube-controller-manager-amd64:v1.11.0k8s.gcr.io/kube-scheduler-amd64:v1.11.0k8s.gcr.io/kube-proxy-amd64:v1.11.0k8s.gcr.......

分秒
昨天
0
0
数据结构--排序

这篇博客包含了数据结构中多种的排序算法: (1)简单选择:第一趟在A[0]~A[n-1]之间找到最小的,与A[0]进行交换,之后在A[1]~A[n-1]之间进行。。。第i趟在A[i-1]~A[n-1]之间找到最小的,最后...

wangxuwei
昨天
1
0
一名3年工作经验的java程序员应该具备的职业技能

一名3年工作经验的Java程序员应该具备的技能,这可能是Java程序员们比较关心的内容。我这里要说明一下,以下列举的内容不是都要会的东西—-但是如果你掌握得越多,最终能得到的评价、拿到的薪...

老道士
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部