{"id":78322,"date":"2024-09-28T16:11:51","date_gmt":"2024-09-28T12:41:51","guid":{"rendered":"https:\/\/nabfollower.com\/blog\/%d9%85%d8%b1%d8%aa%d8%a8-%da%a9%d8%b1%d8%af%d9%86-%da%a9%d8%a7%d8%b1%d8%a7%da%a9%d8%aa%d8%b1-%d8%a8%d8%b1-%d8%a7%d8%b3%d8%a7%d8%b3-%d9%81%d8%b1%da%a9%d8%a7%d9%86%d8%b3-%d8%a7%d9%86%d8%ac%d9%85%d9%86\/"},"modified":"2024-09-28T16:11:51","modified_gmt":"2024-09-28T12:41:51","slug":"%d9%85%d8%b1%d8%aa%d8%a8-%da%a9%d8%b1%d8%af%d9%86-%da%a9%d8%a7%d8%b1%d8%a7%da%a9%d8%aa%d8%b1-%d8%a8%d8%b1-%d8%a7%d8%b3%d8%a7%d8%b3-%d9%81%d8%b1%da%a9%d8%a7%d9%86%d8%b3-%d8%a7%d9%86%d8%ac%d9%85%d9%86","status":"publish","type":"post","link":"https:\/\/nabfollower.com\/blog\/%d9%85%d8%b1%d8%aa%d8%a8-%da%a9%d8%b1%d8%af%d9%86-%da%a9%d8%a7%d8%b1%d8%a7%da%a9%d8%aa%d8%b1-%d8%a8%d8%b1-%d8%a7%d8%b3%d8%a7%d8%b3-%d9%81%d8%b1%da%a9%d8%a7%d9%86%d8%b3-%d8%a7%d9%86%d8%ac%d9%85%d9%86\/","title":{"rendered":"\u0645\u0631\u062a\u0628 \u06a9\u0631\u062f\u0646 \u06a9\u0627\u0631\u0627\u06a9\u062a\u0631 \u0628\u0631 \u0627\u0633\u0627\u0633 \u0641\u0631\u06a9\u0627\u0646\u0633 – \u0627\u0646\u062c\u0645\u0646 DEV"},"content":{"rendered":"

<\/p>\n

\n

\u0645\u0634\u06a9\u0644
\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: \u062a\u0639\u062f\u0627\u062f \u0646\u0648\u06cc\u0633\u0647\u200c\u0647\u0627\u06cc \u0645\u062a\u0645\u0627\u06cc\u0632 (k) \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u062d\u062f\u0627\u06a9\u062b\u0631 256 \u0628\u0627\u0634\u062f\u060c \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u0628\u0627 \u0648\u0627\u0631\u062f \u06a9\u0631\u062f\u0646 k \u0639\u0646\u0627\u0635\u0631 \u062f\u0631 \u0635\u0641 \u0627\u0648\u0644\u0648\u06cc\u062a\u060c \u0632\u0645\u0627\u0646 O(k log k) \u0631\u0627 \u0645\u06cc\u200c\u06af\u06cc\u0631\u062f\u060c \u062c\u0627\u06cc\u06cc \u06a9\u0647 k \u2264 256 \u0627\u0633\u062a. \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646\u060c \u0627\u06cc\u0646 \u0628\u0627 O(256 log \u0645\u062d\u062f\u0648\u062f \u0645\u06cc\u200c\u0634\u0648\u062f. 256) = O(1) \u0632\u06cc\u0631\u0627 \u06cc\u06a9 \u0645\u0642\u062f\u0627\u0631 \u062b\u0627\u0628\u062a \u0627\u0633\u062a.<\/p>\n

TC: \n


\n O<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math><\/span>O<\/span>(<\/span>n<\/span>)<\/span><\/span><\/span><\/span>
\n<\/span><\/p>\n

\u060c O(n) \u0628\u0631\u0627\u06cc \u0627\u06cc\u062c\u0627\u062f \u0622\u0631\u0627\u06cc\u0647 \u0646\u0642\u0634\u0647\u060c + O(1) \u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0635\u0641 \u0647\u06cc\u067e\/\u0627\u0648\u0644\u0648\u06cc\u062a\u060c + O(n) \u0628\u0631\u0627\u06cc \u0627\u06cc\u062c\u0627\u062f \u0631\u0634\u062a\u0647 \u0646\u062a\u06cc\u062c\u0647.<\/p>\n

SC:
\n
\n O<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math><\/span>O<\/span>(<\/span>n<\/span>)<\/span><\/span><\/span><\/span>
\n<\/span><\/p>\n

\u060c \u0628\u0631\u0627\u06cc \u0635\u0641 \u0627\u0648\u0644\u0648\u06cc\u062a \u0628\u0627 \u0627\u0646\u062f\u0627\u0632\u0647 256 = O(1)\u060c + \u0648
\n
\n O<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math><\/span>O<\/span>(<\/span>n<\/span>)<\/span><\/span><\/span><\/span>
\n<\/span><\/p>\n

\u0628\u0631\u0627\u06cc StringBuilder str<\/code><\/p>\n

\n
class<\/span> Solution<\/span> {<\/span>\n    public<\/span> String<\/span> frequencySort<\/span>(<\/span>String<\/span> s<\/span>)<\/span> {<\/span>\n        PriorityQueue<\/span><<\/span>Pair<\/span><<\/span>Character<\/span>,<\/span> Integer<\/span>>><\/span> q<\/span> =<\/span> new<\/span> PriorityQueue<\/span><>((<\/span>a<\/span>,<\/span> b<\/span>)<\/span> -><\/span> b<\/span>.<\/span>getValue<\/span>()<\/span> -<\/span> a<\/span>.<\/span>getValue<\/span>());<\/span>\n\n        int<\/span> map<\/span>[]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>256<\/span>];<\/span>\/\/count of all the ascii characters<\/span>\n        for<\/span> (<\/span>int<\/span> i<\/span> =<\/span> 0<\/span>;<\/span> i<\/span> <<\/span> s<\/span>.<\/span>length<\/span>();<\/span> i<\/span>++)<\/span> {<\/span>\n            map<\/span>[<\/span>s<\/span>.<\/span>charAt<\/span>(<\/span>i<\/span>)]++;<\/span>\n        }<\/span>\n        for<\/span> (<\/span>int<\/span> i<\/span> =<\/span> 0<\/span>;<\/span> i<\/span> <<\/span> map<\/span>.<\/span>length<\/span>;<\/span> i<\/span>++)<\/span> {<\/span>\n            if<\/span> (<\/span>map<\/span>[<\/span>i<\/span>]<\/span> >=<\/span>1<\/span>)<\/span>\n                q<\/span>.<\/span>add<\/span>(<\/span>new<\/span> Pair<\/span>((<\/span>char<\/span>)<\/span> i<\/span>,<\/span> map<\/span>[<\/span>i<\/span>]));<\/span>\n\n        }<\/span>\n        StringBuilder<\/span> str<\/span> =<\/span> new<\/span> StringBuilder<\/span>();<\/span>\n        while<\/span> (!<\/span>q<\/span>.<\/span>isEmpty<\/span>())<\/span> {<\/span>\n            Pair<\/span><<\/span>Character<\/span>,<\/span> Integer<\/span>><\/span> p<\/span> =<\/span> q<\/span>.<\/span>remove<\/span>();<\/span>\n            int<\/span> count<\/span> =<\/span> p<\/span>.<\/span>getValue<\/span>();<\/span>\n            while<\/span> (<\/span>count<\/span>--<\/span> ><\/span> 0<\/span>)<\/span> {<\/span>\n                str<\/span>.<\/span>append<\/span>(<\/span>p<\/span>.<\/span>getKey<\/span>());<\/span>\n            }<\/span>\n        }<\/span>\n        return<\/span> str<\/span>.<\/span>toString<\/span>();<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n
\n
\n    \u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    \n<\/svg><\/p>\n
    \u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    \n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
\u0645\u0634\u06a9\u0644\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: \u062a\u0639\u062f\u0627\u062f \u0646\u0648\u06cc\u0633\u0647\u200c\u0647\u0627\u06cc \u0645\u062a\u0645\u0627\u06cc\u0632 (k) \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u062d\u062f\u0627\u06a9\u062b\u0631 256 \u0628\u0627\u0634\u062f\u060c \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u0628\u0627 \u0648\u0627\u0631\u062f \u06a9\u0631\u062f\u0646 k \u0639\u0646\u0627\u0635\u0631 \u062f\u0631 \u0635\u0641 \u0627\u0648\u0644\u0648\u06cc\u062a\u060c \u0632\u0645\u0627\u0646 O(k log k) \u0631\u0627 \u0645\u06cc\u200c\u06af\u06cc\u0631\u062f\u060c \u062c\u0627\u06cc\u06cc \u06a9\u0647 k \u2264 256 \u0627\u0633\u062a. \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646\u060c \u0627\u06cc\u0646 \u0628\u0627 O(256 log \u0645\u062d\u062f\u0648\u062f \u0645\u06cc\u200c\u0634\u0648\u062f. 256) = O(1) \u0632\u06cc\u0631\u0627 \u06cc\u06a9 \u0645\u0642\u062f\u0627\u0631 \u062b\u0627\u0628\u062a \u0627\u0633\u062a. TC: O(n)O(n)O(n) \u060c O(n) \u0628\u0631\u0627\u06cc \u0627\u06cc\u062c\u0627\u062f \u0622\u0631\u0627\u06cc\u0647 \u0646\u0642\u0634\u0647\u060c + …<\/p>\n","protected":false},"author":2,"featured_media":78323,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"https:\/\/dev.to\/social_previews\/article\/2015989.png","fifu_image_alt":"","footnotes":""},"categories":[339],"tags":[],"class_list":["post-78322","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dev"],"_links":{"self":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts\/78322","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/comments?post=78322"}],"version-history":[{"count":0,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts\/78322\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/media\/78323"}],"wp:attachment":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/media?parent=78322"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/categories?post=78322"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/tags?post=78322"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}