找出字符串

[编程题]找出字符串

热度指数：7313 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string数组str,其是由一个排过序的字符串数组插入了一些空字符串得到的，同时给定数组大小n和需要查找的string x，请用时间复杂度在log级别的算法返回该串的位置(位置从零开始)。

测试样例：

["a","b","","c","","d"],6,"c"

返回：3

算法知识视频讲解

Java

codewind

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)

Java

安徒生的谎言

import java.util.*;

public class Finder {
    public int findString(String[] str, int n, String x) {
        // write code here
        int start=0;
        int end=str.length;
        while(start<=end){
            int mid=(start+end)/2;
            if(str[mid].equals(x)){
                return mid;
            }
            if(str[mid].compareTo(x)>0){
                 end=mid-1;
            }else if(str[mid].compareTo(x)<0){
                start=mid+1;
            }
        }
        return -1;
    }
}

发表于 2018-01-31 14:55:17 回复(1)

Java

Holiday_12138

import java.util.*;

public class Finder {
    public int findString(String[] str, int n, String x) {
        int l=0,r=n-1;
        int lmid,rmid;
        while(l<=r){
            lmid=(l+r)/2;
            rmid=(l+r)/2;
            while(str[lmid]=="")
                lmid--;
            while(str[rmid]=="")
                rmid++;
            if(str[lmid].equals(x))
                return lmid;
            if(str[rmid].equals(x))
                return rmid;
            if(str[lmid].compareTo(x)>0)
                r=lmid-1;
            else
                l=l=rmid+1;
            if(str[rmid].compareTo(x)<0)
                l=rmid+1;
            else
                r=lmid-1;
        }
        return -1;
    }
}

发表于 2017-04-25 20:05:16 回复(0)

Java

风之少年/fw

 public int findString(String[] str, int n, String x) {

        int low = 0;
        int high = str.length - 1;


        //等号不能漏！！
        while (low <= high) {
            int mid = low + (high - low) / 2;


            //如果为空，则对mid进行修正到最近的一个不是空的字符上去
            if (str[mid].isEmpty()) {
                int left = mid - 1;
                int right = mid + 1;
                while (true) {
                    if (left < low && right > high) {
                        return -1;
                    } else if (right <= high && !str[right].isEmpty()) {
                        mid = right;
                        break;
                    } else if (left >= low && !str[left].isEmpty()) {
                        mid = left;
                        break;
                    }
                    right++;
                    left--;
                }
            }

            if (str[mid].equals(x)) {
                return mid;
            } else if (str[mid].compareTo(x) < 0) {//搜索右半边
                low = mid + 1;
            } else if (str[mid].compareTo(x) > 0) {//搜索左半边
                high = mid - 1;
            }

        }

        return -1;
    }

发表于 2016-12-14 16:18:00 回复(0)