{"id":9633,"date":"2022-04-09T23:03:37","date_gmt":"2022-04-10T06:03:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9633"},"modified":"2022-04-09T23:04:15","modified_gmt":"2022-04-10T06:04:15","slug":"leetcode-2231-largest-number-after-digit-swaps-by-parity","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2231-largest-number-after-digit-swaps-by-parity\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2231. Largest Number After Digit Swaps by Parity"},"content":{"rendered":"\n<p>You are given a positive integer&nbsp;<code>num<\/code>. You may swap any two digits of&nbsp;<code>num<\/code>&nbsp;that have the same&nbsp;<strong>parity<\/strong>&nbsp;(i.e. both odd digits or both even digits).<\/p>\n\n\n\n<p>Return<em>&nbsp;the&nbsp;<strong>largest<\/strong>&nbsp;possible value of&nbsp;<\/em><code>num<\/code><em>&nbsp;after&nbsp;<strong>any<\/strong>&nbsp;number of swaps.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = 1234\n<strong>Output:<\/strong> 3412\n<strong>Explanation:<\/strong> Swap the digit 3 with the digit 1, this results in the number 3214.\nSwap the digit 2 with the digit 4, this results in the number 3412.\nNote that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.\nAlso note that we may not swap the digit 4 with the digit 1 since they are of different parities.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = 65875\n<strong>Output:<\/strong> 87655\n<strong>Explanation:<\/strong> Swap the digit 8 with the digit 6, this results in the number 85675.\nSwap the first digit 5 with the digit 7, this results in the number 87655.\nNote that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= num &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<p>Solution:<\/p>\n\n\n\n<p>Put all even digits into one array, all odd digits into another one, all digits into the third. Sort two arrays, and generate a new number from sorted arrays.<\/p>\n\n\n\n<p>Time complexity: O(logn*loglogn)<br>Space complexity: O(logn)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int largestInteger(int num) {\n    vector<int> odd, even, org;\n    for (int cur = num; cur; cur \/= 10) {\n      ((cur & 1) ? odd : even).push_back(cur % 10);\n      org.push_back(cur % 10);\n    }\n    sort(begin(odd), end(odd));\n    sort(begin(even), end(even));    \n    int ans = 0;\n    for (int i = 0; i < org.size(); ++i) {\n      if (i) ans *= 10;\n      auto&#038; cur = (org[org.size() - i - 1] &#038; 1) ? odd : even;\n      ans += cur.back();\n      cur.pop_back();\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a positive integer&nbsp;num. You may swap any two digits of&nbsp;num&nbsp;that have the same&nbsp;parity&nbsp;(i.e. both odd digits or both even digits). Return&nbsp;the&nbsp;largest&nbsp;possible value&#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],"tags":[222,524,317,15],"class_list":["post-9633","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-generation","tag-largest","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9633","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=9633"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9633\/revisions"}],"predecessor-version":[{"id":9635,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9633\/revisions\/9635"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}