题解 | #重排字符串#

class Solution {
public:

    string rearrangestring(string str) {
        string ret;
        int arr[26] = { 0 };//建立哈希表，统计出现的字符
        int n = str.size();
        int m = 0;//记录出现最多的字符个数
        char c = 0;//记录出现最多的字符
        for(int i=0;i<n;i++)
        {
            int a = str[i] - 'a';
            if(++arr[a]>m)
            {
                m = arr[a];
                c = str[i];
            }
        }
        if(m>(n+1)/2) return ret;//如果出现最多的字符大于总个数的一半，则不满足

        char ch[100010];//按奇偶的方式重排字符
        int x = 0;//先排偶

        //先将最多的字符排好
        while(m--)
        {
            ch[x] = c;
            x += 2;
        }

        for(int j=0;j<26;j++)
        {
            if(arr[j] && j + 'a' != c)
            {
                while(arr[j]--)
                {
                    if(x>=n) x = 1;//再排奇
                    ch[x] = j + 'a';
                    x += 2;
                }
            }
        }
        for(int a=0;a<n;a++)
        {
            ret += ch[a];
        }
        return ret;
    }
};