{"id":1373,"date":"2020-06-26T21:33:34","date_gmt":"2020-06-27T04:33:34","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1373"},"modified":"2020-06-26T21:35:23","modified_gmt":"2020-06-27T04:35:23","slug":"boyer-moore-majority-vote","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/06\/26\/boyer-moore-majority-vote\/","title":{"rendered":"Boyer\u2013Moore Majority Vote"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>No one is supposed to invent the Boyer\u2013Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here. <\/p>\n\n\n\n<p><strong>Please remember to increase <code>cnt<\/code> first, then check if <code>cnt==0<\/code>, and finally decrease <code>cnt<\/code>. <\/strong><\/p>\n\n\n\n<p>Several good points here to mention, <\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>There&#8217;s only one majority number if it exists; <\/li><li>If we eliminate the same number of majority numbers and non-majority numbers, the majority number still has larger frequencies than other numbers. <\/li><li>If a <code>cnt<\/code> turns into <code>0<\/code>, it means we have met the same number of majority numbers and non-majority numbers.<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"> n\/2<\/h3>\n\n\n\n<p>Given a non-empty array of size\u00a0<em>n<\/em>, find the majority element. The majority element is the element that appears\u00a0<strong>more than<\/strong>\u00a0<code>\u230a n\/2 \u230b<\/code>\u00a0times.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int cnt = 0;\nint cand = ll{INT_MIN} - 1;\nfor (auto num : nums) {\n    if (num == cand) {\n        cnt++;\n    } else if (cnt == 0) {\n        cand = num;\n        cnt = 1;  \n    } else {\n        cnt--;\n    }\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">n\/3<\/h3>\n\n\n\n<p>Given a non-empty array of size\u00a0<em>n<\/em>, find all majority elements. The majority element is the element that appears\u00a0<strong>more than<\/strong>\u00a0<code>\u230a n\/3 \u230b<\/code>\u00a0times.<\/p>\n\n\n\n<p>The order of branches are extremely tricky here. <\/p>\n\n\n\n<p>The correct order should avoid <code>cand0<\/code> and <code>cand1<\/code> get the same value, so at first we should check if the current value is in the two candidates or not. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">ll cand0 = ll{INT_MIN} - 1, cnt0 = 0;\nll cand1 = ll{INT_MIN} - 1, cnt1 = 0;\n\nfor (auto num : nums) {\n    if (cand1 == num) {\n        cnt1++;\n    } else if (cand0 == num) {\n        cnt0++;\n    } else if (cnt1 == 0) {\n        cand1 = num;\n        cnt1 = 1;\n    } else if (cnt0 == 0) {\n        cand0 = num;\n        cnt0 = 1;\n    } else {\n        cnt0--;\n        cnt1--;\n    }\n}<\/code><\/pre>\n\n\n\n<p>The following order will fail in case <code>[1,2,2,3,2,1,1,3]<\/code>. Since at index <code>3<\/code>, <code>cnt1<\/code> will turn into <code>0<\/code>, so at index4 <code>cnt1<\/code> will be the <code>2<\/code>, which causes duplication. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">for (auto num : nums) {\n    if (cand1 == num) {\n        cnt1++;\n    }  else if (cnt1 == 0) {\n        cand1 = num;\n        cnt1 = 1;\n    } else if (cand0 == num) {\n        cnt0++;\n    } else if (cnt0 == 0) {\n        cand0 = num;\n        cnt0 = 1;\n    } else {\n        cnt0--;\n        cnt1--;\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary No one is supposed to invent the Boyer\u2013Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here. Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt. Several good points here to mention,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1373","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1373","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1373"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1373\/revisions"}],"predecessor-version":[{"id":1379,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1373\/revisions\/1379"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}