{"id":374,"date":"2012-05-17T14:58:08","date_gmt":"2012-05-17T06:58:08","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=374"},"modified":"2020-06-06T14:58:48","modified_gmt":"2020-06-06T06:58:48","slug":"%e7%ba%bf%e6%80%a7%e6%97%b6%e9%97%b4%e9%80%89%e6%8b%a9","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=374","title":{"rendered":"\u7ebf\u6027\u65f6\u95f4\u9009\u62e9"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u7ebf\u6027\u65f6\u95f4\u9009\u62e9\n \npackage wkx;\n \nimport java.io.IOException;\nimport java.util.Date;\nimport java.util.Random;\nimport java.util.Scanner;\n \npublic class Test {\n \n\tprivate static int randomPartition(int&#91;] data, int beg, int end) {\n\t\tRandom rand = new Random(new Date().getTime());\n\t\tint pos = rand.nextInt(end - beg + 1) + beg;\n\t\tSystem.out.println(\"pos=\" + pos);\n\t\tint t = data&#91;beg];\n\t\tdata&#91;beg] = data&#91;pos];\n\t\tdata&#91;pos] = t;\n \n\t\tint key = data&#91;beg];\n\t\twhile (beg &lt; end) {\n\t\t\twhile (beg &lt; end &amp;&amp; data&#91;end] >= key)\n\t\t\t\tend--;\n\t\t\tdata&#91;beg] = data&#91;end];\n\t\t\twhile (beg &lt; end &amp;&amp; data&#91;beg] &lt;= key)\n\t\t\t\tbeg++;\n\t\t\tdata&#91;end] = data&#91;beg];\n\t\t}\n\t\tdata&#91;beg] = key;\n\t\treturn beg;\n\t}\n \n\tprivate static int select(int&#91;] data, int beg, int end, int k) {\n\t\tif (beg == end)\n\t\t\treturn data&#91;beg];\n\t\tint mid = randomPartition(data, beg, end);\n\t\tint size = mid - beg + 1;\n\t\tif (k &lt;= size)\n\t\t\treturn select(data, beg, mid, k);\n\t\telse\n\t\t\treturn select(data, mid + 1, end, k - size);\n\t}\n \n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;] data = new int&#91;100];\n\t\tScanner in = new Scanner(System.in);\n\t\twhile (in.hasNextInt()) {\n\t\t\tint len = in.nextInt();\n\t\t\tint k = in.nextInt();\n\t\t\tfor (int i = 0; i &lt; len; i++)\n\t\t\t\tdata&#91;i] = in.nextInt();\n\t\t\tSystem.out.println(select(data, 0, len - 1, k));\n\t\t}\n\t}\n \n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-374","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=374"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=374"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}