{"id":149482,"date":"2020-08-26T09:09:56","date_gmt":"2020-08-26T01:09:56","guid":{"rendered":"http:\/\/4563.org\/?p=149482"},"modified":"2020-08-26T09:09:56","modified_gmt":"2020-08-26T01:09:56","slug":"%e5%b7%a8%e7%a1%ac%e5%ae%b6%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e6%90%9c%e7%b4%a2%e6%97%8b%e8%bd%ac%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84%ef%bc%88%e4%b8%ad%e7%ad%89%e9%9a%be%e5%ba%a6%ef%bc%89","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=149482","title":{"rendered":"\u5de8\u786c\u5bb6\u9762\u8bd5\u9898\uff1a\u641c\u7d22\u65cb\u8f6c\u6392\u5e8f\u6570\u7ec4\uff08\u4e2d\u7b49\u96be\u5ea6\uff09"},"content":{"rendered":"
\n
\n
\n

\u5de8\u786c\u5bb6\u9762\u8bd5\u9898\uff1a\u641c\u7d22\u65cb\u8f6c\u6392\u5e8f\u6570\u7ec4\uff08\u4e2d\u7b49\u96be\u5ea6\uff09 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 9<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u5047\u8bbe\u6709\u4e00\u4e2a\u6392\u5e8f\u7684\u6309\u672a\u77e5\u7684\u65cb\u8f6c\u8f74\u65cb\u8f6c\u7684\u6570\u7ec4(\u6bd4\u5982\uff0c0 1 2 4 5 6 7 \u53ef\u80fd\u6210\u4e3a 4 5 6 7 0 1 2)\u3002\u7ed9\u5b9a\u4e00\u4e2a\u76ee\u6807\u503c\u8fdb\u884c\u641c\u7d22\uff0c\u5982\u679c\u5728\u6570\u7ec4\u4e2d\u627e\u5230\u76ee\u6807\u503c\u8fd4\u56de\u6570\u7ec4\u4e2d\u7684\u7d22\u5f15\u4f4d\u7f6e\uff0c\u5426\u5219\u8fd4\u56de-1 \u3002\u4f60\u53ef\u4ee5\u5047\u8bbe\u6570\u7ec4\u4e2d\u4e0d\u5b58\u5728\u91cd\u590d\u7684\u5143\u7d20\u3002<\/p>\n

\u770b\u9898\u89e3\u4e4b\u524d\uff0c\u53ef\u4ee5\u8bd5\u8bd5\u2192\u5728\u7ebf\u505a\u9898<\/p>\n

\u4f8b 1:<\/h2>\n
\u8f93\u5165: [4, 5, 1, 2, 3] and target=1,  \u8f93\u51fa: 2. <\/code><\/pre>\n
\u4f8b 2:<\/h2>\n
\u8f93\u5165: [4, 5, 1, 2, 3] and target=0,  \u8f93\u51fa: -1. <\/code><\/pre>\n
[\u9898\u89e3]<\/h1>\n
 <\/p>\n
\u7b97\u6cd5\uff1a\u4e8c\u5206<\/h2>\n
    \n
  • \u6839\u636e\u9898\u76ee\u6211\u4eec\u53ef\u4ee5\u77e5\u9053\u65cb\u8f6c\u6570\u7ec4\u5b9e\u9645\u4e0a\u662f\u4e24\u4e2a\u9012\u589e\u6570\u7ec4\u7684\u7ec4\u6210\uff0c\u4e14\u7b2c\u4e00\u4e2a\u6570\u7ec4\u4e2d\u7684\u6700\u5c0f\u503c\u5927\u4e8e\u7b2c\u4e8c\u4e2a\u6570\u7ec4\u7684\u6700\u5927\u503c<\/li>\n
  • \u7531\u4e8e\u6570\u7ec4\u4e2d\u4e0d\u5b58\u5728\u91cd\u590d\u7684\u5143\u7d20\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u5148\u627e\u5230 target \u5728\u54ea\u4e2a\u6570\u7ec4\uff0c\u518d\u8fdb\u884c\u4e8c\u5206<\/li>\n<\/ul>\n
    \u4ee3\u7801\u601d\u8def<\/h2>\n
      \n
    • \u4e8c\u5206\u627e\u5230\u7b2c\u4e8c\u4e2a\u6570\u7ec4\u7684\u8d77\u59cb\u4f4d\u7f6e\uff0c\u5373\u6574\u4e2a\u6570\u7ec4\u7684\u6700\u5c0f\u503c\u7684\u4f4d\u7f6e minPosition<\/li>\n
    • \u901a\u8fc7\u6bd4\u8f83 target \u548c\u7b2c\u4e8c\u4e2a\u6570\u7ec4\u6700\u5c0f\u5143\u7d20\uff08\u5373\u6700\u540e\u4e00\u4e2a\u6570\uff09\u5927\u5c0f\u5173\u7cfb\u5224\u65ad target \u5728\u54ea\u4e00\u4e2a\u6570\u7ec4<\/li>\n
    • \u5bf9 target \u6240\u5728\u7684\u6570\u7ec4\u4e8c\u5206<\/li>\n<\/ul>\n
      \u590d\u6742\u5ea6\u5206\u6790<\/h2>\n
      N \u8868\u793a\u4e3a A \u6570\u7ec4\u7684\u957f\u5ea6<\/p>\n
        \n
      • \u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(N)<\/li>\n
      • \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(logN)<\/li>\n<\/ul>\n
        public class Solution {     \/**      * @param A: an integer rotated sorted array      * @param target: an integer to be searched      * @return: an integer      *\/     public int search(int[] A, int target) {         if (A == null || A.length == 0) {              return -1;          }                       \/\/\u627e\u5230\u6570\u7ec4\u6700\u5c0f\u503c\u4f4d\u7f6e minPosition\uff0c\u5373\u7b2c\u4e8c\u4e2a\u6570\u7ec4\u7684\u8d77\u59cb\u4f4d\u7f6e         int minPosition = 0;          intleft = 0;          int right = A.length - 1;          while (left + 1 < right) {              int mid = left + (right - left) \/ 2;              if (A[mid] > A[right]) {                 left = mid;              } else {                  right = mid;              }          }                                if (A[left] < A[right]) {              minPosition = left;          } else {              minPosition = right;          }                        \/\/\u5224\u65ad target \u5728\u54ea\u4e00\u4e2a\u6570\u7ec4\u4e2d         if (A[A.length - 1] < target) {              left = 0;              right = minPosition - 1;          } else {              left = minPosition;              right = A.length - 1;          }                       \/\/\u5bf9 target \u6240\u5728\u6570\u7ec4\u4e8c\u5206\u641c\u7d22         while (left + 1 < right) {              int mid = left + (right - left) \/ 2;              if (A[mid] < target) {                  left = mid;              } else {                  right = mid;              }          }                                if (A[left] == target) {              return left;          }          if (A[right] == target) {              return right;          }                  return -1;      } }   <\/code><\/pre>\n
        \u70b9\u6b64\u5904\u67e5\u770b\u66f4\u591a\u9898\u89e3<\/p>\n<\/p><\/div>\n
        <\/p>\n
         \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (22<\/span>)        <\/div>\n
         <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
          \n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : dragonbuf <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u5443\uff0c\u8fd9\u90fd\u5c5e\u4e8e\u5fc5\u5237\u7684\u9898\u4e86\u5427\u3002 \u4e8c\u5206\u554a \u52a8\u6001\u89c4\u5212\u554a \u56de\u6eaf\u554a \u4e8c\u53c9\u6811\u904d\u5386\u554a \u5806\u554a\u3002 \u9898\u4e3b\u4e0d\u5982\u6574\u4e2a CPU \u3000\u6309\u6b63\u5f26\u66f2\u7ebf\u5206\u5e03\u8fd9\u79cd\u89e3\u6790\uff0c\u8ba9\u6211\u7b49\u5b66\u4e60\u5b66\u4e60                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : littlewing <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u5e38\u89c4\u9898\uff0c\u5e94\u8be5\u5c5e\u4e8e easy                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : chanlk <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u7ecf\u5178\u9898\u4e86,\u5982\u679c\u628a\u6761\u4ef6\u6539\u6210\u53ef\u4ee5\u5b58\u5728\u91cd\u590d\u5143\u7d20,\u77ac\u95f4\u5c31\u6076\u5fc3\u591a\u4e86                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : lihongming <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       @chanlk leetcode \u4e0a\u6709\u53ef\u91cd\u590d\u7684\u90a3\u4e2a\u9898                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : chanlk <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       @lihongming \u662f\u7684,\u6211\u8e29\u8fc7\u8fd9\u5751\u54c8\u54c8                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : yaxe <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u4f4d\u8fd0\u7b97\u4e0d\u9999\u4e48 python<\/p>\n
          class Solution:
           def search(self, nums, target):
           lo, hi = 0, len(nums) – 1
           while lo < hi:
           mid = (lo + hi) \/\/ 2
           if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]):
           lo = mid + 1
           else:
           hi = mid
           return lo if lo == hi and target == nums[lo] else -1                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : tongyang <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       leetcode \u539f\u9898\u5440                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : levelworm <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u6211\u53ea\u4f1a loop \u3002\u3002\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : mogami18 <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u4e2d\u7b49\u96be\u5ea6???                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : mjyywd <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u7b2c\u4e00\uff1a\u8fd9\u4e0d\u662f\u5de8\u786c\u7684\u9898\u76ee\u3002
          \u7b2c\u4e8c\uff1a\u8fd9\u662f\u67d0\u4e2a\u57f9\u8bad\u673a\u6784\u6216\u8005\u5237\u9898\u7f51\u7ad9\u7684\u5f15\u6d41\u8d34\u3002
          \u6240\u4ee5\u6211\u62d2\u7edd\u89e3\u7b54\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : hsuvee <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u4e8c\u5206\u67e5\u627e\u90fd\u6210\u4e86 medium\uff0c\u96be\u9053\u7237\u9752\u56de\u4e86\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : 20015jjw <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u8fd9\u9898\u8fd9\u662f\u4e2d\u7b49\u96be\u5ea6
          \u5404\u4f4d\u5927\u4f6c\u522b\u770b\u4e0d\u8d77
          \u6211\u8fdb instagram \u95ee\u7684\u5c31\u8fd9\u9898\u539f\u9898                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : luojianxhlxt <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u5de8\u786c\u5bb6\u7684\u9898\uff0c\u90fd\u6ca1 C#\u7684\u4e48                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : zvl0reqglvd <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u5219\u9898\u7b80\u5355\u554a\uff0c\u4f46\u662f\u4f60\u505a\u7684\u6709\u70b9\u590d\u6742\u5427\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : Banxiaozhuan <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       leetcode \u539f\u9898\u3002\u3002\u3002\u3002\u3002\u3002\u3002\u6709\u6bdb\u597d\u8ba8\u8bba\u7684\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : yaphets666 <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u8fd9\u9898\u662f\u4ec0\u4e48\u610f\u601d\u5462?\u5c31\u770b\u4f60\u4f1a\u4e0d\u4f1a\u4e8c\u5206?\u8fd8\u662f\u600e\u4e48\u8bf4 \u6709\u70b9\u8ff7\u60d1                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : paulee <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u4e8c\u5206\u5e94\u8be5\u53ea\u7528\u4e00\u6b21\u5c31\u884c                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : blurryWu <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       @hsuvee \u4e8c\u5206\u67e5\u627e hard \u9898\u4e00\u5927\u5806\u3002\u662f\u4e2d\u7b49\u96be\u5ea6\uff0c\u6211\u5bfb\u601d\u4e5f\u6ca1\u5565\u95ee\u9898\u5440\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : bilibalao <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u8fd9\u9898\u8d3c\u7b80\u5355\u554a\u3002\u3002\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : shm7 <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u53eb\u4e8c\u5206\u6216\u8005\u501f\u9274\u6392\u5e8f\u91cc\u9762\u7684 pivot \u3002\u8fd9\u4e2a\u6570\u8981\u4e48\u7b49\u4e8e start\/end\/pivot\uff0c\u8981\u4e48\u5c31\u5728 start-pivot\/pivot-end \u4e4b\u95f4\uff0c\u6bcf\u6b21\u9009\u4e00\u4e2a pivot \u90fd\u80fd\u628a\u8303\u56f4\u7f29\u5c0f\u4e00\u534a\u3002O(logn).                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : guana <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u8fd9\u662f\u5e7f\u544a                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n
          \n
          \n
           \u8cc7\u6df1\u5927\u4f6c : liuyx7894 <\/span>  <\/div>\n
           <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                       \u5982\u679c\u662f\u7eaf\u65e0\u5e8f\u6570\u7ec4\uff0c\u7528\u4ec0\u4e48\u7b97\u6cd5\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
        • \n","protected":false},"excerpt":{"rendered":"
          \u5de8\u786c\u5bb6\u9762\u8bd5\u9898\uff1a\u641c\u7d22\u65cb\u8f6c\u6392\u5e8f\u6570\u7ec4\uff08\u4e2d…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/149482"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=149482"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/149482\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=149482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=149482"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=149482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}