{"id":424,"date":"2021-11-24T21:43:54","date_gmt":"2021-11-24T13:43:54","guid":{"rendered":"http:\/\/liyanliang.net\/?p=424"},"modified":"2021-12-12T08:00:38","modified_gmt":"2021-12-12T00:00:38","slug":"find-diff-number","status":"publish","type":"post","link":"http:\/\/liyanliang.net\/index.php\/2021\/11\/24\/find-diff-number\/","title":{"rendered":"\u7b97\u6cd5\uff1a\u5bfb\u627e\u5f02\u5e38\u6570\u5b57"},"content":{"rendered":"\n<div id=\"toc_container\" class=\"no_bullets\"><p class=\"toc_title\">Contents<\/p><ul class=\"toc_list\"><li><a href=\"#i\"><span class=\"toc_number toc_depth_1\">1<\/span> \u9898\u76ee\u63cf\u8ff0\uff1a<\/a><\/li><li><a href=\"#1\"><span class=\"toc_number toc_depth_1\">2<\/span> \u89e3\u6cd51\uff1a\u66b4\u529b\u89e3\u6cd5<\/a><\/li><li><a href=\"#i-2\"><span class=\"toc_number toc_depth_1\">3<\/span> \u89e3\u6cd5\u4e8c\uff1a\u4e8c\u5206\u6cd5<\/a><\/li><\/ul><\/div>\n<h3 class=\"has-cyan-bluish-gray-background-color has-background wp-block-heading\"><span id=\"i\">\u9898\u76ee\u63cf\u8ff0\uff1a<\/span><\/h3>\n\n\n\n<p>\u5bfb\u627e\u5f02\u5e38\u6570\u5b57\u3002 \u8f93\u5165\u4e00\u4e2a\u65e0\u5e8f\u7684\u516c\u5dee\u4e3a1\u7684\u7b49\u5dee\u6570\u5217\uff0c\u5176\u4e2d\u6709\u4e00\u4e2a\u6570\u4e0d\u5c5e\u4e8e\u6b64\u6570\u5217\uff0c\u627e\u5230\u8fd9\u4e2a\u6570\u3002<\/p>\n\n\n\n<p>\u4e3e\u4f8b\uff1a \u8f93\u51651 3 2 3 \uff0c \u8f93\u51fa\u4e3a3 \u8f93\u51652 5 3 7 4\uff0c\u8f93\u51fa7<\/p>\n\n\n\n<h3 class=\"has-cyan-bluish-gray-background-color has-background wp-block-heading\"><span id=\"1\">\u89e3\u6cd51\uff1a\u66b4\u529b\u89e3\u6cd5<\/span><\/h3>\n\n\n\n<p>\u901a\u8fc7\u4ece\u5934\u5230\u5c3e\u904d\u5386\u6570\u7ec4\uff0c\u627e\u5230\u5f02\u5e38\u7684\u6570\u5b57\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int GetExceptionalNumber(int arr[], int n)\n{\n    if (arr == nullptr || n &lt; 3)\n    {\n        return -1;\n    }\n\u200b\n    QuickSort(arr, n);\n\u200b\n    for (int i = 1; i &lt; n; ++i)\n    {\n        if (arr[i] - arr[i-1] == 1)\n        {\n            continue;\n        }\n\u200b\n        if (i &lt; n-1)\n        {\n            if (arr[i+1] - arr[i] == 1)\n            {\n                return arr[i-1];\n            }\n            else\n            {\n                return arr[i];\n            }\n        }\n        else \/\/ (i-1) != 0\n        {\n            if (arr[i-1] - arr[i-2] == 1)\n            {\n                return arr[i];\n            }\n            else\n            {\n                return arr[i-1];\n            }\n        }\n\u200b\n    }\n\u200b\n    return -1; \/\/ not found\n}<\/pre>\n\n\n\n<h3 class=\"has-cyan-bluish-gray-background-color has-background wp-block-heading\"><span id=\"i-2\">\u89e3\u6cd5\u4e8c\uff1a\u4e8c\u5206\u6cd5<\/span><\/h3>\n\n\n\n<p>\u4f7f\u7528\u4e8c\u5206\u67e5\u627e\u7684\u65b9\u6cd5\uff0c\u8fd9\u91cc\u7684\u5173\u952e\u662f\u600e\u4e48\u786e\u5b9a\u76ee\u6807\u6570\u5b57\u3002\u8fd9\u91cc\u6709\u4e24\u4e2a\u5173\u952e\u70b9\uff1a1.\u6570\u7ec4\u7684\u516c\u5dee\u4e3a1 \uff1b2.\u6392\u5e8f\u540e\uff0c\u6570\u7ec4\u662f\u6709\u5e8f\u7684\u3002 \u5982\u6b64\uff0c\u53ef\u901a\u8fc7\u5224\u65ad\u6570\u5b57\u4e0e\u6570\u5b57\u7684\u4e0b\u6807\u662f\u5426\u76f8\u7b49\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image is-style-default\"><img decoding=\"async\" src=\"https:\/\/liyanliangpublic.oss-cn-hongkong.aliyuncs.com\/img\/20211124213944.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int GetExceptionalNumber(int arr[], int n)\n{\n    if (arr == nullptr || n &lt; 3)\n    {\n        return -1;\n    }\n\u200b\n    QuickSort(arr, n);\n\u200b\n    \/\/ \u5224\u65ad\u7b2c\u4e00\u4e2a\u4e3a\u5f02\u5e38\u6570\n    if (arr[1] - arr[0] != 1)\n    {\n        if (arr[2] - arr[1] == 1)\n        {\n            return arr[0];\n        }\n    }\n\u200b\n    int startNumber = arr[0];\n    int l = 0;\n    int r = n - 1;\n    while (l &lt;= r)\n    {\n        int midIndex = l + (r-l)\/2;\n        if (l == r)\n        {\n            return arr[midIndex];\n        }\n\u200b\n        int midNumber = midIndex+startNumber;\n        if (midNumber > arr[midIndex])\n        {\n            r = midIndex-1;\n        }\n        else \/\/ midNumber == arr[midIndex]\n        {\n            if (midIndex &lt; n-1 &amp;&amp; arr[midIndex+1] == arr[midIndex])\n            {\n                return arr[midIndex];\n            }\n            else if (midIndex > 0 &amp;&amp; arr[midIndex-1] == arr[midIndex])\n            {\n                return arr[midIndex];\n            }\n            else\n            {\n                l = midIndex+1;\n            }   \n        }\n    }\n\u200b\n    return -1; \/\/ not found\n}<\/pre>\n\n\n\n<p><strong>\u4ee3\u7801\u4e2d\u7528\u5230\u7684\u5feb\u901f\u6392\u5e8f\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\u200b\ntemplate &lt;typename T>\nvoid swap(T* lhs, T* rhs)\n{\n    T temp = *lhs;\n    *lhs = *rhs;\n    *rhs = temp;\n}\n\u200b\ntemplate &lt;typename T>\nint partition(T arr[], int l, int r)\n{\n    int mid = l + (r-l)\/2;\n    int randIdx = std::rand()%(r-l+1)+l;\n    swap(&amp;arr[l], &amp;arr[randIdx]);\n    T v = arr[l];\n    int j = l;\n    for (int i = l+1; i &lt;= r; i++)\n    {\n        if (arr[i] &lt; v)\n        {\n            j++;\n            swap(&amp;arr[i], &amp;arr[j]);\n        }\n    }\n\u200b\n    swap(&amp;arr[l], &amp;arr[j]);\n    return j;\n}\n\u200b\ntemplate &lt;typename T>\nvoid __QuickSort(T arr[], int l, int r)\n{\n    if (l >= r)\n    {\n        return;\n    }\n\u200b\n    int q = partition(arr, l, r);\n    __QuickSort(arr, l, q);\n    __QuickSort(arr, q+1, r);\n\u200b\n}\n\u200b\ntemplate &lt;typename T>\nvoid QuickSort(T arr[], int n)\n{\n    if (arr == nullptr || n &lt; 0)\n    {\n        return;\n    }\n\u200b\n    __QuickSort(arr, 0, n-1);\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Contents1 \u9898\u76ee\u63cf\u8ff0\uff1a2 \u89e3\u6cd51\uff1a\u66b4\u529b\u89e3\u6cd53 \u89e3\u6cd5\u4e8c\uff1a\u4e8c\u5206\u6cd5 \u9898\u76ee\u63cf\u8ff0\uff1a \u5bfb\u627e\u5f02\u5e38\u6570\u5b57\u3002 \u8f93\u5165\u4e00\u4e2a\u65e0\u5e8f\u7684\u516c\u5dee\u4e3a1\u7684\u7b49\u5dee\u6570\u5217\uff0c\u5176\u4e2d\u6709\u4e00\u4e2a\u6570\u4e0d\u5c5e\u4e8e\u6b64\u6570\u5217\uff0c\u627e\u5230\u8fd9\u4e2a\u6570\u3002 \u4e3e\u4f8b\uff1a \u8f93\u51651 3 2 3 \uff0c \u8f93\u51fa\u4e3a3 \u8f93\u51652 5 3 7 4\uff0c\u8f93\u51fa7 \u89e3\u6cd51\uff1a\u66b4\u529b\u89e3\u6cd5 \u901a\u8fc7\u4ece\u5934\u5230\u5c3e\u904d\u5386\u6570\u7ec4\uff0c\u627e\u5230\u5f02\u5e38\u7684\u6570\u5b57\u3002 \u89e3\u6cd5\u4e8c\uff1a\u4e8c\u5206\u6cd5 \u4f7f\u7528\u4e8c\u5206\u67e5\u627e\u7684\u65b9\u6cd5\uff0c\u8fd9\u91cc\u7684\u5173\u952e\u662f\u600e\u4e48\u786e\u5b9a\u76ee\u6807\u6570\u5b57\u3002\u8fd9\u91cc\u6709\u4e24\u4e2a\u5173\u952e\u70b9\uff1a1.\u6570\u7ec4\u7684\u516c\u5dee\u4e3a1 \uff1b2.\u6392\u5e8f\u540e\uff0c\u6570\u7ec4\u662f\u6709\u5e8f\u7684\u3002 \u5982\u6b64\uff0c\u53ef\u901a\u8fc7\u5224\u65ad\u6570\u5b57\u4e0e\u6570\u5b57\u7684\u4e0b\u6807\u662f\u5426\u76f8\u7b49\u3002 \u4ee3\u7801\u4e2d\u7528\u5230\u7684\u5feb\u901f\u6392\u5e8f\uff1a<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[45],"class_list":["post-424","post","type-post","status-publish","format-standard","hentry","category-44","tag-45"],"_links":{"self":[{"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/posts\/424","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/comments?post=424"}],"version-history":[{"count":3,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/posts\/424\/revisions"}],"predecessor-version":[{"id":439,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/posts\/424\/revisions\/439"}],"wp:attachment":[{"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/media?parent=424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/categories?post=424"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/liyanliang.net\/index.php\/wp-json\/wp\/v2\/tags?post=424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}