程序员面试金典-10.05-稀疏矩阵搜索

刺骨的言语ヽ痛彻心扉 2022-09-09 02:23 138阅读 0赞

## 程序员面试金典-10.05-稀疏矩阵搜索 ##

稀疏矩阵搜索，采用二分法，跳过“”空字符串

稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
    
    示例1:
    
     输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
     输出：-1
     说明: 不存在返回-1。
    示例2:
    
     输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
     输出：4
    提示:
    
    words的长度在[1, 1000000]之间
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/sparse-array-search-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

int devide_find(char ** words,int wordsSize,int start,int end,int mid,char *s);
    
    int findString(char** words, int wordsSize, char* s){
        
        int start = 0;
        int end = wordsSize - 1;
    
        while(strcmp(words[start],"")==0 && start<wordsSize)
            start++;
        while(strcmp(words[end],"")==0 && end>-1)
            end--;
        char * s1 = words[start];
        char * s2 = words[end];
        if(start>end || strcmp(s,s1)<0 || strcmp(s2,s)<0 )
            return -1;
        
        int mid = (start+end)/2;
        int ret = devide_find(words,wordsSize,start,end,mid,s);
        return ret;
    }
    
    int devide_find(char ** words,int wordsSize,int start,int end,int mid,char *s){
        
        if(start>end)
            return -1;
        if(strcmp(words[mid],s)==0)
            return mid;
        if(strcmp(words[mid],"")==0){
        
            int p = mid;
            int q = mid;
            while(strcmp(words[p],"")==0 && p>=start){
        
                p--;
            }
            if(strcmp(words[p],s)==0){
        
                return p;
            }
            else if(strcmp(words[p],s)<0){
        
                while(strcmp(words[q],"")==0 && q<=end){
        
                    q++;
                }
                return devide_find(words,wordsSize,q,end,(q+end)/2,s);
            }
            else 
                return devide_find(words,wordsSize,start,p-1,(p-1+start)/2,s);
        }
        else{
        
            if(strcmp(words[mid],s)<0){
        
                return devide_find(words,wordsSize,mid+1,end,(mid+1+end)/2,s);
            }
            else{
        
                return devide_find(words,wordsSize,start,mid-1,(mid-1+start)/2,s);
            }
        }
    }