{"id":1176,"date":"2017-12-11T07:44:02","date_gmt":"2017-12-11T15:44:02","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1176"},"modified":"2017-12-11T20:06:52","modified_gmt":"2017-12-12T04:06:52","slug":"leetcode-744-find-smallest-letter-greater-than-target","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-744-find-smallest-letter-greater-than-target\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 744. Find Smallest Letter Greater Than Target"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 744. Find Smallest Letter Greater Than Target - \u5237\u9898\u627e\u5de5\u4f5c EP128\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/nxJXnQ7wLhM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given a list of sorted characters\u00a0<code>letters<\/code>\u00a0containing only lowercase letters, and given a target letter\u00a0<code>target<\/code>, find the smallest element in the list that is larger than the given target.<\/p>\n<p>Letters also wrap around. For example, if the target is\u00a0<code>target = 'z'<\/code>\u00a0and\u00a0<code>letters = ['a', 'b']<\/code>, the answer is\u00a0<code>'a'<\/code>.<\/p>\n<p><b>Examples:<\/b><\/p>\n<pre class=\"\">Input:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"a\"\r\nOutput: \"c\"\r\n\r\nInput:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"c\"\r\nOutput: \"f\"\r\n\r\nInput:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"d\"\r\nOutput: \"f\"\r\n\r\nInput:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"g\"\r\nOutput: \"j\"\r\n\r\nInput:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"j\"\r\nOutput: \"c\"\r\n\r\nInput:\r\nletters = [\"c\", \"f\", \"j\"]\r\ntarget = \"k\"\r\nOutput: \"c\"\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><code>letters<\/code>\u00a0has a length in range\u00a0<code>[2, 10000]<\/code>.<\/li>\n<li><code>letters<\/code>\u00a0consists of lowercase letters, and contains at least 2 unique letters.<\/li>\n<li><code>target<\/code>\u00a0is a lowercase letter.<\/li>\n<\/ol>\n<p><strong>Link:\u00a0<\/strong><a href=\"https:\/\/leetcode.com\/problems\/find-smallest-letter-greater-than-target\/description\/\">https:\/\/leetcode.com\/problems\/find-smallest-letter-greater-than-target\/description\/\u00a0<\/a><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<ol>\n<li>Scan the array Time complexity: O(n)<\/li>\n<li>Binary search\u00a0Time complexity: O(logn)<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1182 size-full\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/744-ep128.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/744-ep128.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/744-ep128-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/744-ep128-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Solution 1:<\/strong><\/p>\n<p>C++ \/ Scan<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 16 ms\r\nclass Solution {\r\npublic:\r\n    char nextGreatestLetter(vector&lt;char&gt;&amp; letters, char target) {\r\n        for (const char c : letters)\r\n            if (c &gt; target) return c;\r\n        return letters.front();\r\n    }\r\n};<\/pre>\n<p>C++ \/ Set<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 16 ms\r\nclass Solution {\r\npublic:\r\n    char nextGreatestLetter(vector&lt;char&gt;&amp; letters, char target) {\r\n        vector&lt;int&gt; seen(26, 0);\r\n        for (const char c : letters)\r\n            seen[c - 'a'] = 1;\r\n        \r\n        while (true) {\r\n            if (++target &gt; 'z') target = 'a';\r\n            if (seen[target - 'a']) return target;            \r\n        }\r\n        \r\n        return ' ';\r\n    }\r\n};<\/pre>\n<p>C++ \/ Binary Search<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 15 ms\r\nclass Solution {\r\npublic:\r\n    char nextGreatestLetter(vector&lt;char&gt;&amp; letters, char target) {\r\n        int l = 0;\r\n        int r = letters.size();\r\n        while (l &lt; r) {\r\n            const int m = l + (r - l) \/ 2;\r\n            if (letters[m] &lt;= target)\r\n                l = m + 1;\r\n            else\r\n                r = m;\r\n        }\r\n        return letters[l % letters.size()];\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given a list of sorted characters\u00a0letters\u00a0containing only lowercase letters, and given a target letter\u00a0target, find the smallest element in the list that is larger&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,149],"tags":[52,185],"class_list":["post-1176","post","type-post","status-publish","format-standard","hentry","category-array","category-binary-search","tag-binary-search","tag-sorted","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1176","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1176"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1176\/revisions"}],"predecessor-version":[{"id":1194,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1176\/revisions\/1194"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}