《Cracking the Coding Interview》——第9章：递归和动态规划—

2014-03-20 03:01

题目：给定一个已按升序排序的数组，找出是否有A[i] = i的情况出现。

解法1：如果元素不重复，是可以严格二分查找的。

代码：

 // 9.3 Given a unique sorted array, find a position where A[i] = i, if one exists.

 #include <cstdio>

 #include <vector>

 using namespace std;

 int main()

 {

     vector<int> v;

     int n;

     int i;

     int ll, rr, mm;

     while (scanf("%d", &n) ==  && n > ) {

         v.resize(n);

         for (i = ; i < n; ++i) {

             scanf("%d", &v[i]);

         }

         if (v[] >  || v[n - ] < n - ) {

             mm = -;

         } else {

             ll = ;

             rr = n - ;

             while (ll <= rr) {

                 mm = (ll + rr) / ;

                 if (v[mm] < mm) {

                     ll = mm + ;

                 } else if (v[mm] > mm) {

                     rr = mm - ;

                 } else {

                     break;

                 }

             }

             if (ll > rr) {

                 mm = -;

             }

         }

         printf("%d\n", mm);

         v.clear();

     }

     return ;

 }

解法2：如果元素可能存在重复，那么会出现无法确定答案在左边还是右边的时候。比如{-1, 3, 3, 3, 3}，后面的连续4个‘3’中有A[i]<i，有A[i]>i，也有A[i]=i的。这种情况下就得两边都进行查找了。在没有重复的时候，还是可以二分的，因此总体复杂度介于O(log(n))和O(n)之间，依数据好坏而变。

代码：

 // 9.3 Given a sorted array, find a position where A[i] = i, if one exists. The array may have duplicates.

 #include <cstdio>

 #include <vector>

 using namespace std;

 int findMagicIndex(vector<int> &v, int start, int end)

 {

     if (start > end || start > (int)v.size() -  || end < ) {

         return -;

     }

     int mid = (start + end) / ;

     if (v[mid] == mid) {

         return mid;

     }

     int res = findMagicIndex(v, start, (mid -  < v[mid] ? mid -  : v[mid]));

     if (res >= ) {

         return res;

     }

     res = findMagicIndex(v, (mid +  > v[mid] ? mid +  : v[mid]), end);

     return res;

 }

 int main()

 {

     vector<int> v;

     int n;

     int i;

     while (scanf("%d", &n) ==  && n > ) {

         v.resize(n);

         for (i = ; i < n; ++i) {

             scanf("%d", &v[i]);

         }

         printf("%d\n", findMagicIndex(v, , n - ));

         v.clear();

     }

     return ;

 }

巴特西

《Cracking the Coding Interview》——第9章：递归和动态规划——题目3

最新文章

热门文章