{"id":9842,"date":"2022-09-26T09:57:17","date_gmt":"2022-09-26T16:57:17","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9842"},"modified":"2022-09-26T09:57:47","modified_gmt":"2022-09-26T16:57:47","slug":"leetcode-2418-sort-the-people","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2418-sort-the-people\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2418.\u00a0Sort the People"},"content":{"rendered":"\n

You are given an array of strings names<\/code>, and an array heights<\/code> that consists of distinct<\/strong> positive integers. Both arrays are of length n<\/code>.<\/p>\n\n\n\n

For each index i<\/code>, names[i]<\/code> and heights[i]<\/code> denote the name and height of the ith<\/sup><\/code> person.<\/p>\n\n\n\n

Return names<\/code> sorted in descending<\/strong> order by the people’s heights<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> names = [\"Mary\",\"John\",\"Emma\"], heights = [180,165,170]\nOutput:<\/strong> [\"Mary\",\"Emma\",\"John\"]\nExplanation:<\/strong> Mary is the tallest, followed by Emma and John.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> names = [\"Alice\",\"Bob\",\"Bob\"], heights = [155,185,150]\nOutput:<\/strong> [\"Bob\",\"Alice\",\"Bob\"]\nExplanation:<\/strong> The first Bob is the tallest, followed by Alice and the second Bob.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == names.length == heights.length<\/code><\/li>
  • 1 <= n <= 103<\/sup><\/code><\/li>
  • 1 <= names[i].length <= 20<\/code><\/li>
  • 1 <= heights[i] <= 105<\/sup><\/code><\/li>
  • names[i]<\/code> consists of lower and upper case English letters.<\/li>
  • All the values of heights<\/code> are distinct.<\/li><\/ul>\n\n\n\n
    Solution: Zip and sort<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector sortPeople(vector& names, vector& heights) {\n    vector> data;\n    for (int i = 0; i < names.size(); ++i)\n      data.emplace_back(heights[i], &names[i]);    \n    sort(rbegin(data), rend(data));\n    vector ans(names.size());\n    for (int i = 0; i < names.size(); ++i)\n      ans[i].swap(*data[i].second);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n. For each index i, names[i] and heights[i] denote the name and height…<\/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":[20,222,23,785],"class_list":["post-9842","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-easy","tag-sort","tag-zip","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9842","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=9842"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9842\/revisions"}],"predecessor-version":[{"id":9844,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9842\/revisions\/9844"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9842"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9842"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}