{"id":3168,"date":"2018-07-14T22:43:37","date_gmt":"2018-07-15T05:43:37","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3168"},"modified":"2018-08-27T08:11:28","modified_gmt":"2018-08-27T15:11:28","slug":"leetcode-870-advantage-shuffle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-870-advantage-shuffle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 870. Advantage Shuffle"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given two arrays\u00a0A<\/code>\u00a0and\u00a0B<\/code>\u00a0of equal size, the\u00a0advantage of\u00a0A<\/code>\u00a0with respect to\u00a0B<\/code><\/em>\u00a0is the number of indices\u00a0i<\/code>\u00a0for which\u00a0A[i] > B[i]<\/code>.<\/p>\n

Return\u00a0any<\/strong>\u00a0permutation of\u00a0A<\/code>\u00a0that maximizes its advantage with respect to\u00a0B<\/code>.<\/p>\n

\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>A = [2,7,11,15]<\/span>, B = [1,10,4,11]<\/span>\r\nOutput: <\/strong>[2,11,7,15]<\/span>\r\n<\/pre>\n
\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>A = [12,24,8,32]<\/span>, B = [13,25,32,11]<\/span>\r\nOutput: <\/strong>[24,32,8,12]<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length = B.length <= 10000<\/code><\/li>\n
  2. 0 <= A[i] <= 10^9<\/code><\/li>\n
  3. 0 <= B[i] <= 10^9<\/code><\/li>\n<\/ol>\n
    \u00a0<\/ins><\/p>\n
    Solution: Greedy \u7530\u5fcc\u8d5b\u9a6c<\/strong><\/h1>\n
    Use the smallest unused number A[j] in A such that A[j] > B[i], if not possible, use the smallest number in A.<\/p>\n
    Time complexity: O(nlogn)<\/p>\n
    Space complexity: O(n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 124 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> advantageCount(vector<int>& A, vector<int>& B) {\r\n    multiset<int> s(begin(A), end(A));\r\n    vector<int> ans;    \r\n    for (int b : B) {\r\n      auto it = s.upper_bound(b);\r\n      if (it == s.end()) it = s.begin();      \r\n      ans.push_back(*it);\r\n      s.erase(it);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
     <\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given two arrays\u00a0A\u00a0and\u00a0B\u00a0of equal size, the\u00a0advantage of\u00a0A\u00a0with respect to\u00a0B\u00a0is the number of indices\u00a0i\u00a0for which\u00a0A[i] > B[i]. Return\u00a0any\u00a0permutation of\u00a0A\u00a0that maximizes its advantage with respect to\u00a0B.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[320,177,335,15],"class_list":["post-3168","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-inversion","tag-medium","tag-multiset","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3168","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=3168"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3168\/revisions"}],"predecessor-version":[{"id":3724,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3168\/revisions\/3724"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}