面試金典--11.5

題目描述：給定排序后的字符串數組，中間有一些空串，要求找到給定字符串的位置

思路：

（1）遍歷，最慢的

（2）二分查找，當mid處為空串，就找到最近的非空串繼續尋找。如果需要找空串？（單獨處理）

  1 #include <iostream>
  2 #include <queue>
  3 #include <climits>
  4 #include <algorithm>
  5 #include <memory.h>
  6 #include <stdio.h>
  7 #include <ostream>
  8 #include <vector>
  9 #include <list>
 10 #include <cmath>
 11 #include <string>
 12 #include <stdexcept>
 13 #include <stack>
 14 #include <map>
 15 using namespace std;
 16 
 17 int fun(vector<string> a,string target)
 18 {
 19     int l = 0;
 20     int r = a.size() - 1;
 21     while(l <= r)
 22     {
 23         int mid = (l+r)/2;
 24         if(a[mid] == target)
 25         {
 26             return mid;
 27         }
 28         else if(a[mid] == "")
 29         {
 30             int k = mid + 1;
 31             while(k <= r)
 32             {
 33                 if(a[k] != "")
 34                     break;
 35             }
 36             if(k <= r)
 37             {
 38                 if(a[k] == target)
 39                 {
 40                     return k;
 41                 }
 42                 else if(a[k] > target)
 43                 {
 44                     r = k - 1;
 45                 }
 46                 else if(a[k] < target)
 47                 {
 48                     l = k + 1;
 49                 }
 50             }
 51             else
 52             {
 53                 k = mid - 1;
 54                 while(k >= l)
 55                 {
 56                     if(a[k] != "")
 57                         break;
 58                 }
 59                 if(k >= l)
 60                 {
 61                     if(a[k] == target)
 62                     {
 63                         return k;
 64                     }
 65                     else if(a[k] > target)
 66                     {
 67                         r = k - 1;
 68                     }
 69                     else if(a[k] < target)
 70                     {
 71                         l = k + 1;
 72                     }
 73                 }
 74                 else
 75                     return -1;
 76             }
 77         }
 78         else if(a[mid] > target)
 79         {
 80             r = mid - 1;
 81         }
 82         else if(a[mid] < target)
 83         {
 84             l = mid + 1;
 85         }
 86     }
 87 }
 88 
 89 int main()
 90 {
 91     vector<string> input;
 92     input.push_back("at");
 93     input.push_back("");
 94     input.push_back("");
 95     input.push_back("");
 96     input.push_back("ball");
 97     input.push_back("");
 98     input.push_back("");
 99     input.push_back("car");
100     input.push_back("");
101     input.push_back("");
102     input.push_back("dad");
103     input.push_back("");
104     input.push_back("");
105     cout<<fun(input,"ball")<<endl;
106     return 0;
107 }

轉載于:https://www.cnblogs.com/cane/p/3810769.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/258474.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/258474.shtml
英文地址，請注明出處：http://en.pswp.cn/news/258474.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！