[LeetCode] 451.文字出現頻度によるソート(Medium)C言語の問題解

タイトル

は文字列を指定します.文字列の中の文字を出現する頻度に従って降順に並べてください.

例
①例1

入力:「tree」

出力:「eert」

は,'e'は2回,'r'と't'はいずれも1回しか現れないと説明した.|したがって、‘e’は‘r’および’t’の前に現れなければならない.また、「eetr」も有効な答えです.

②例2

入力:「cccaaa」

出力:「cccaaa」

は、「c」と「a」が3回現れたと説明した.また、「aaaccc」も有効な答えです.|「cacacaca」は正しくありません.同じアルファベットを一緒に置かなければならないからです.

③例3

入力:「Aabb」

出力:「bbaa」

解釈:「bbaA」も有効な答えですが、「Aabb」は正しくありません.|注意‘A’と‘a’は2つの異なる文字であると考えられる.

説明
①データ範囲(自己測定)

0 <= s[i] < 128

②関連話題

ハッシュ表

スタック

ソート

文字列

③類似テーマ

347. 前K個の高周波要素-力ボタン網

347. Top K Frequent Elements — leetcode

387. 文字列の最初の一意の文字-バックル

387. First Unique Character in a String — leetcode

④タイトル住所

451. 文字の出現頻度に基づいてソート-バックル

451. Sort Characters By Frequency — leetcode

解題方法
①ハッシュテーブル+ソート

データの範囲は約0~128であり、配列シミュレーションのハッシュテーブルで解くことができ、速度が最も速い(空間で時間を変える).

各文字の出現回数をハッシュテーブルで記録し、2次元整数配列を新規作成し、1列目に具体的な文字のASC②コードを記録し、2列目に文字の出現回数を記録し、1列目に対応する.

は、その後、出現回数を大きくから小さく並べ替えて、文字列内の文字を出現頻度に従って降順に並べ替える.

時間複雑度:O(Nlogn).

空間複雑度:O(N).

②ハッシュテーブル+文字配列

各文字の出現回数をハッシュ表で記録し、行の下付き文字の出現回数に対応する2次元文字配列を新規作成し、行の文字列は出現回数==行の下付き文字の総和を記録し、これにより「間接」に出現回数をソートし、時間の複雑さを低減することができる.

時間複雑度:O(N).

空間複雑度:O(N).(爆発...)

ps:この方法で長い間振り回されていましたが...その結果、空間の複雑さが高すぎて、テストに合格できないことがわかりました.長い間コードを修正してやっと提出した後、運行速度が遅くなったことに気づいた.暴力的に解くほうがましだ.
③ハッシュ表(uthash)

配列シミュレーションのハッシュテーブルで解くのは直感的であるが、メモリ空間を浪費するため、uthashを使用するのがより良い方法である.

uthashはC言語で記述されたオープンソースライブラリであり、マクロを用いてハッシュテーブルの削除変更などの機能を実現している.

はuthashで異なる文字の出現回数を統計し、それに付属するソート機能を使用してキー値(文字)を出現回数に従ってソートし、最後にハッシュテーブルを巡回すればよい.

時間複雑度:O(N).

空間複雑度:O(N).

コードの詳細

ハッシュテーブル+ソート

//     (  )。
//   :     arr[i][0](           )。
int compare(const void* a, const void* b) {
    return ((int*)b)[0]-((int*)a)[0]; 
}

char* frequencySort(char* s) {
    int hash[128] = {0}, arr[128][2] = {0}, len = strlen(s), size = 0;
   
    //    。
    for (int i = 0; i < len; i++) 
        hash[s[i]]++;
    for (int i = 0; i < 128; i++) {
        //                 。
        if (hash[i] > 0) {
            arr[size][0] = hash[i];
            arr[size][1] = i;
            size++;
        }
    }
         
    //          。
    qsort(arr, size, sizeof(arr[0]), compare);
    
    //      。
    for (int i = 0, j = 0; i < size; i++) {
        if (arr[i][0] > 0) {
            s[j++] = arr[i][1];
            arr[i][0]--;
            i--;
        }
    }
    
    return s;
}

ハッシュテーブル+文字配列

char* frequencySort(char* s) {
    int hash[128] = {0}, len = strlen(s);
    char** arr = malloc(sizeof(char*)*(len+1));
    
    //    。
    for (int i = 0; i < len; i++) {
        hash[s[i]]++;
        arr[i] = malloc(sizeof(char)*1);   
        strcpy(arr[i], "");
    }
    
    arr[len] = malloc(sizeof(char)*1);
    strcpy(arr[len], "");
    strcpy(s, "");

    for (int i = 0; i < 128; i++) {
        if (hash[i] > 0) {
            int count = hash[i], l = strlen(arr[hash[i]]);
            char* s1 = malloc(sizeof(char)*(len+1));
            //       。
            char s2[2];
            s2[0] = i;
            s2[1] = '\0';
            
            if (strcmp(arr[hash[i]], "") == 0) {
                arr[hash[i]] = malloc(sizeof(char)*(count+1));
                strcpy(arr[hash[i]], "");
            }
            //            。
            else {
                strcpy(s1, arr[hash[i]]);
                arr[hash[i]] = malloc(sizeof(char)*(count+l+1));
                strcpy(arr[hash[i]], s1);
            }
            
            //       。
            while (count > 0) {
                strcat(arr[hash[i]], s2);             
                count--;
            }
        }
    }
    //      。
    for (int i = len; i > 0; i--) {
        if (strlen(arr[i]) > 0)
            strcat(s, arr[i]);
    }
    
    return s;
}

ハッシュテーブル

// uthash    c        ，                 。
struct hash {
    int key;
    int count;
    UT_hash_handle hh; 
};

//     。
int count_sort(struct hash* a, struct hash* b) {
    return b->count - a->count;
}

char* frequencySort(char* s) { 
    struct hash* hashTable = NULL;
    int len = strlen(s);
    char* result = malloc(sizeof(char)*(len+1));
    strcpy(result, "");
    
    //                。
    for (int i = 0; i < len; i++) {
        struct hash* h;
        int n = s[i];
        HASH_FIND_INT(hashTable, &n, h);
        
        if (!h) {
            h = malloc(sizeof(struct hash));
            h->key = s[i];
            h->count = 1;
            HASH_ADD_INT(hashTable, key, h);
        }
        else
            h->count++;
    }
    
    //          (  )。
    HASH_SORT(hashTable, count_sort);
    
    //          。
    for (struct hash* s = hashTable; s != NULL; s = s->hh.next) {
        while (s->count > 0) {
            char s1[2];
            s1[0] = s->key;
            s1[1] = '\0';
            strcat(result, s1);
            s->count--;
        }
    }
    
    return result;
}

ふろく

私の個人ブログ:messi 1002.top

間違いや疑問があれば連絡してください[email protected]

所有题目解答:fork me on github