重排字符串

# -*- coding: utf-8 -*-

import collections


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/6c3a5604cf274b2287fbe27c5dc74743?tpId=196&tqId=40510&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：居梇梇
    算法：
        1. 统计每个字符出现的次数，collections.Counter(str)
        2. 获取出现次数最多的字符的出现次数，判断是否能够填充
        3. 对count按字符出现次数进行排序
        4. 将排序结果，转化为字符数组data，如[('d', 4), ('a', 1), ('c', 1), ('b', 1)] ==> ['d', 'd', 'd', 'd', 'a', 'c', 'b']
        5. 取数组data的前后两部分，进行交叉合并
    复杂度：
        时间复杂度：O(mlogm + m + n/2), m为count的长度, n为字符串的长度
        空间复杂度：O(m)
    """

    def rearrangestring(self, s):
        # write code here
        n = len(s)

        if not s&nbs***bsp;n == 1:
            return s

        count = collections.Counter(s) # 统计s中每个字符出现次数
        maxCount = max(count.values())
        if maxCount > (n + 1) // 2: # 判断是否能够填充
            return ""

        count = sorted(count.items(), key=lambda x: -x[1]) # 按字符出现次数对count进行排序，sorted支持对可迭代对象排序，sort只支持列表排序
        # print count

        data = []
        for k, v in count:
            data += [k] * v
        # print data

        # m = (n + 1) // 2
        # i, j, res = 0, m, ""
        # while i < m and j < n: # 遍历的方式进行合并，不通过
        #     res += data[i] + data[j]
        #     i += 1
        #     j += 1
        # if i < m:
        #     res += data[i]
        # return res

        res = ["" for _ in range(len(s))]

        res[::2], res[1::2] = data[:(n + 1) // 2], data[(n + 1) // 2:]

        return "".join(res)


if __name__ == "__main__":
    sol = Solution()

    # str = "abcdd"

    # str = "nowcoder"

    # str = "aaab"

    # str = "cdarzo"

    # str = "aaaabbbb"

    # str = "wlrbbmqb"

    str = "abcdddd"

    res = sol.rearrangestring(str)

    print res