给定一个string数组str,其是由一个排过序的字符串数组插入了一些空字符串得到的，同时给定数组大小n和需要查找的string x，请用时间复杂度在log级别的算法返回该串的位置(位置从零开始)。
测试样例：
["a","b","","c","","d"],6,"c"
返回：3
[编程题]找出字符串
import java.util.*;
/*
思路：这题目是二分法的变种，空格就左移一步，为防止越界，要先判断左右两边是不是为空格,先找到左右两边都不是空格再开始
但是不得不说，在空串>>子串的时候，复杂度还是O（n），不过如果不过滤掉空串直接动手做的话我只想得到这种方法
*/
public class Finder {
public int findString(String[] str, int n, String x) {
if(str==null||str.length==0) return -1;
int start =0;
int end=n-1;
while(str[start]==""){
start++;
if(start==n) return -1;
}//先找到左右两边都不是空格的端点
while(str[end]==""){
end--;
}
while(start<=end){
int mid =(start+end)/2;
while(str[mid]=="") mid--;
if(str[mid].compareTo(x)==0) return mid;
else if(str[mid].compareTo(x)>0){
end =mid-1;
while(str[end]=="") end--;
}
else {
start=mid+1;
while(str[start]=="") start++;
}
}
return -1;
}
}
运行时间：42ms
占用内存：9564k
发表于 2017-06-30 14:40:09
回复(0)
每一次都过掉查找子串开头和结尾的空格，那么就可以保证头和尾部都没有空格。
那么剩下就是处理中间字符串的空格了。
处理完以后就是正常的二分查找。
看了一下跟大家的思路相比，自己想的这个算是比较简洁了，与诸位分享一波。
class Finder {
public:
int findString(vector<string> str, int n, string x) {
// write code here
int low = 0;
int high = str.size() - 1;
int mid = 0;
while(low <= high) {
while (str[low] == "" && low < high) low ++;
while (str[high] == "" && low < high) high --;
mid = (low + high) >> 1;
if (str[mid] == x) return mid;
while (str[mid] == "" && mid > low) mid--;
if (str[mid].compare(x) > 0) high = mid - 1;
else low = mid + 1;
}
return -1;
}
};
发表于 2019-01-22 11:40:46
回复(2)
我承认这是欺骗自己！！
ArrayList<String> arrayList = new ArrayList<>();
for(int i=0;i<str.length;i++){
arrayList.add(str[i]);
}
return arrayList.indexOf(x);
发表于 2017-07-30 21:06:39
回复(2)
二分查找修改版，若遇到空串，先向左找第一个非空，找不到再向右。
平均O(longn)，最差O(n)。运行时间1ms。
class Finder {
public:
int findString(vector<string> str, int n, string x)
{
int left = 0, right = n - 1;
while (str[left] == "") ++left;
while (str[right] == "") --right;
while (left < right)
{
if(str[left] == x) return left;
if(str[right] == x) return right;
int mid = (left + right) >> 1;
if (str[mid] == "")
{
int _left = mid - 1;
while (_left > left && str[_left] == "") --_left;
if (_left != left) mid = _left;
else
{
int _right = mid + 1;
while (_right < right && str[_right] == "") ++_right;
mid = _right;
}
}
if (x == str[mid]) return mid;
else if (x < str[mid]) right = mid - 1;
else left = mid + 1;
}
return left;
}
};
发表于 2017-06-29 17:36:51
回复(0)
class Finder {
public:
int findString(vector<string> str, int n, string x) {
// write code here
/*方法1，顺序查找
if(n<=0) return -1;
for(int i=0;i<n;i++)
if(str[i]==x)
return i;
return -1;*/
//思路2，二分查找，空格单独处理
int start=0,end=n-1;
int mid;
while(start<=end)
{
mid=(start+end)/2;
//假如是空格，向左（或向右）找到第一个不为空的字符
if(str[mid]=="")
{
int index=mid;
while(index>=start && str[index]=="") --index;
if(index<start) start=mid+1;//一直到最左边都是空格，那么只能在右半边查找
else if(str[index]==x) return index;//左边第一个非空字符等于x，直接返回下标
else if(str[index]>x) end=mid-1;//左边第一个非空字符串大于x，那只能继续向左查找
else start=mid+1;//否则，向右查找
}
else
{
if(str[mid]==x) return mid;
else if(str[mid]>x) end=mid-1;
else start=mid+1;
}
}
return -1;
}
};
发表于 2016-08-18 14:38:03
回复(0)
class Finder {
public:
int findString(vector<string> str, int n, string x) {
int l=0, r=str.size()-1, m=0;
while(l<=r){
while(str[l]=="" && l<r)
l++;
while(str[r]=="" && l<r)
r--;
m = (l+r)>>1;
if(str[m]==x)
return m;
while(str[m]=="" && l<r)
m--;
if(str[m]>x)
r = m-1;
else
l = m+1; }
return -1;
}
};
发表于 2019-03-04 01:40:48
回复(0)
log复杂度，锁定 快排，堆排，归并，二分, 这里考虑快速排序:
# -*- coding:utf-8 -*-
class Finder:
def findString(self, s, n, x):
# write code here
left = []
right = []
for i in range(n):
if s[i] > x:
right.append(s[i])
elif s[i] < x:
left.append(s[i])
else:
return s.index(x)
if findString(left, len(left), x):
return findString(left, len(left), x)
return findString(right, len(right), x)
发表于 2017-07-02 21:49:41
回复(2)
//java version. the most important thing is to deal with the void(mid="") import java.util.*; public class Finder { public int findString(String[] str, int n, String x) { if(str == null || n == 0 || x == null || x == ""){ return -1; } int start = 0, end = n-1; while(start <= end){ int mid = start + (end - start) / 2; int left = mid - 1; int right = mid + 1; if(str[mid].isEmpty()){ while(true){ if(left < start && end < right){ return -1; }else if(start < left && !str[left].isEmpty()){ mid = left; break; }else if(right < end && !str[right].isEmpty()){ mid = right; break; } left--; right++; } } if(str[mid].equals(x)){ return mid; }else if(str[mid].compareTo(x) < 0){ start = mid + 1; }else{ end = mid - 1; } } return -1; } }
发表于 2017-05-21 23:04:45
回复(0)
public int findString(String[] str, int n, String x) {
for (int l = 0, r = n - 1; l <= r; ) {
int m = (l + r) / 2;
for (int i = m, j = m; ; ) { //过掉空字符串
if (i >= l) {
if (str[i].isEmpty())
i--;
else {
m = i;
break;
}
} else if (j <= r) {
if (str[j].isEmpty())
j++;
else {
m = j;
break;
}
} else
return -1;
}
if (str[m].compareTo(x) > 0)
r = m - 1;
else if (str[m].compareTo(x) < 0)
l = m + 1;
else
return m;
}
return -1;
}
发表于 2017-01-19 15:59:31
回复(0)
class Finder { public: int half_find(vector<string> str,int start,int end,string x){ if(start > end) return -1; int mid = (start + end)/2; if(str[mid] == ""){ int res1 = half_find(str,start,mid-1,x); if(res1 != -1) return res1; int res2 = half_find(str,mid+1,end,x); if(res2!= -1) return res2; } else{ if(str[mid] == x) return mid; else if(str[mid] < x) return half_find(str,mid+1,end,x); else return half_find(str,start,mid-1,x); } return -1; } int findString(vector<string> str, int n, string x) { // write code here if(n == 0) return 0; return half_find(str,0,n-1,x); } };
发表于 2016-09-07 11:17:59
回复(1)
思路：
二分查找的变形，如果中间元素为空字符串，那么找出离它最近的非空字符串即可。
其他步骤跟二分查找一样
# -*- coding:utf-8 -*-
class Finder:
def findString(self, s, n, x):
if n < 1:
return -1
i = 0
j = n - 1
while i <= j:
mid = (i + j)/2
# 移动mid位置
if s[mid] == '':
left = mid - 1
right = mid + 1
while True:
if left < i and right > j:
return -1
elif left >= i and s[left] != '':
mid = left
break
elif right <= j and s[right] != '':
mid = right
break
right += 1
left -= 1
if s[mid] == x:
return mid
elif s[mid] < x:
i = mid + 1
else:
j = mid - 1
return -1
发表于 2016-08-08 14:50:27
回复(0)
public static int findString(String[] str, int n, String x) {
// write code here
if (str == null || 0 == n || x == null || x == "") {
return -1;
}
int start = 0;
int end = n - 1;
while (start < end) {
int mid = start + (end - start) >> 1;
int left = mid - 1;
int right = mid + 1;
if (str[mid].isEmpty()) {
while (true) {
if (start > left && end < right) {
return -1;
} else if (start < left && !str[left].isEmpty()) {
mid = left;
break;
} else if (end > right && !str[right].isEmpty()) {
mid = right;
break;
}
left--;
right++;
}
}
if (str[mid].equals(x)) {
return mid;
} else if (str[mid].compareTo(x) < 0) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
大家可以看下这个题的代码，根据程序员面试金典上的递归代码改进而来的，我根据该题的测试用例进行测试一下，没出什么问题，但一直提交不成功。求大神解答
发表于 2016-03-31 16:53:30
回复(3)
Solution: 二分查找，只是比较string是否相等要用 str1.equals(str2)， 比较string
大小要用str1.compareTo(str2).
public int findString(String[] str, int n, String x) {
// write code here
if(str==null || str.length==0) return -1;
int start=0,end=str.length-1;
int mid=0;
while(start+1<end){
mid = start + (end-start)/2;
if(x.equals(str[mid])){
return mid;
}
if(x.compareTo(str[mid])>0){
start=mid;
}else{
end=mid;
}
}
if(x.equals(str[start])){
return start;
}
if(x.equals(str[end])){
return end;
}
return -1;
}
发表于 2016-01-02 11:49:41
回复(0)
思路
这是一道二分查找 的变形题目。唯一的关注点就是当str[mid] ==
""时的处理，此时仅通过str[mid]=""是无法判断目标是在mid的左边还是右边。所以，我们遍历mid左边的元素找到第一个不是空字符串的元素。
如果mid左边的所有元素都是空字符串，则去掉令start=mid+1；
否则
找到第一个不是空字符串的元素下标为index
（1）如果str[index]等于目标正好返回。
（2）如果str[index]大于目标，则说明目标在str[index]左边，令end = index - 1。
（3）如果str[index]小于目标，则说明目标在str[mid]右边，令start = mid + 1
代码
class Finder {
public:
int findString(vector<string> str, int n, string x) {
int size = str.size();
if(size == 0 || n <= 0){
return -1;
}//if
// 采用二分查找
int start = 0,end = size - 1;
int mid;
while(start <= end){
mid = (end - start) / 2 + start;
// 遇到空格特殊处理
if(str[mid] == ""){
int index = mid;
while(index >= start && str[index] == ""){
--index;
}//while
if(index < start){
start = mid + 1;
}//if
else if(str[index] == x){
return index;
}//else
else if(str[index] > x){
end = index - 1;
}//else
else{
start = mid + 1;
}//else
}//if
// 非空格
else{
// 找到目标
if(str[mid] == x){
return mid;
}//if
// 中间值比目标大只能在中间值的左边
else if(str[mid] > x){
end = mid - 1;
}//else
// 中间值比目标小只能在中间值的右边
else{
start = mid + 1;
}//else
}//else
}//while
return -1;
}
};
发表于 2015-08-18 22:14:16
回复(10)
# -*- coding:utf-8 -*- class Finder: def findString(self, s, n, x): # write code here if n <= 0: return -1 low = 0 high = n - 1 while low <= high: while s[low] == '' and low < high: # 过滤左边空格 low += 1 while s[high] == '' and low < high: # 过滤右边空格 high -= 1 mid = (low + high) // 2 if s[mid] == x: return mid while s[mid] == '' and low < high: # 过滤中间空格 mid -= 1 if s[mid] > x: # 大于要查找的x，high往左移动，使得mid也往左移动 high -= 1 else: low += 1 # 小于要查找的x，high往右移动，使得mid也往右移动 return -1 # 没有找到x，返回-1
发表于 2020-12-13 00:44:48
回复(0)
import java.util.*;
public class Finder {
public int findString(String[] str, int n, String x) {
if (n <=0) return -1;
// write code here
int l =0, r = str.length -1;
while (l<=r) {
int mid = l+ (r-l)/2;
if (str[mid].length() ==0) {
int index = mid;
while ( index>=l && str[index].length()==0){
--index;
}
if (index < l) {
//[l,mid ]一直都是空格，不用找了
l = mid +1;
}
else if(str[index] ==x) {
return index;
}else if(str[index].compareTo(x) >0) {
r = mid -1;
}else{
l = mid +1;
}
}else {
if(str[mid].equals(x)) {
return mid;
}else if (str[mid].compareTo(x) >0) {
//amid > x
r = mid -1;
}else{
l = mid +1;
}
}
}
return -9999;
}
}
发表于 2020-11-19 15:56:29
回复(0)
class Finder {
public:
int findString(vector<string> str, int n, string x) {
//使用折半查找法
int location;
if(n<=0)
{
return location;
}
int mid = n/2;
int front = 0;
int back = n;
while(front < back)
{
mid = (front + back) / 2;
if(str[mid] != " ")
{
if(x > str[mid] )
{
front = mid + 1;
}
else if( x < str[mid])
{
back = mid - 1;
}
else
{
return mid;
}
}
else if(str[mid] == " ")
{
if(x > str[mid+1])
{
front = mid + 2;
}
else if(x < str[mid-1])
{
back = mid - 2;
}
else{
return mid;
}
}
}
}
};
发表于 2020-08-02 22:07:41
回复(0)
整体还是好理解的，多加一种情况，参考代码
class Finder {
public:
int findString(vector<string> str, int n, string x) {
// write code here
int left = 0;
int right = n-1;
while(left <= right){
int mid = left+(right-left)/2;
if(str[mid] == x){
return mid;
}
// 这种情况是新增加的
else if(str[mid] == ""){
if(mid >0 && str[mid-1] < x){
left = mid+1;
}else if(mid >0 && str[mid-1] > x){
right = mid-1;
}
}
else if(str[mid] > x){
right = mid-1;
}
else if(str[mid] < x){
left = mid+1;
}
}
return left;
}
};
发表于 2020-07-01 09:35:10
回复(0)
问题信息
难度：
70条回答
34收藏
15720浏览
通过挑战的用户
查看代码-
2023-02-16 15:03:48
-
2023-02-13 14:31:55 -
2022-09-13 09:49:30 -
2022-08-25 10:40:03
-
2022-08-20 21:11:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
