1

我正在尝试编写一种算法，以按频率顺序重新排列字符串中的字母，然后按字母顺序排列。例如，“apple”变成“aelpp”。“香蕉”变成了“bnnaaa”。

我知道多种语言，但我现在使用 Python 来编写代码。这是我到目前为止所拥有的，但它不起作用，因为没有频率排序。

def order(word):
  word = word.lower()
  storage = [0] * 26
  for c in word:
    storage[ord(c) - 97] += 1
  newWord = []
  for l, c in enumerate(storage):
    for i in range(0, storage[l]):
      newWord.append(chr(l + 97))
  return ''.join(newWord)

关于如何最有效地正确实施此算法的任何建议？

4

2 回答 2

2

这是一个（大部分）pythonic示例，说明如何在python中处理这个问题，我希望评论足以解释正在发生的事情：

words = ["apples", "banannas", "oranges"]

def main():
    # our list of jumbled words
    jumbled = []
    for word in words:
        # dictionary of letter / frequency pairs.
        letters = {};
        # get letter frequency
        for letter in word:
            if letter in letters:
                letters[letter] += 1
            else:
                letters[letter] = 1
        # sort the letter / frequency pairs on descending frequency
        jumbled_word = sorted(letters.items(), key = lambda x: x[1],
                                                              reverse = True)
        # join the letters back together and add to our jumbled words
        jumbled.append(''.join([x[0] for x in jumbled_word]))
        letters = {}

    # print out the jumbled words in alphabetical order
    for x in sorted(jumbled):
        print x

if __name__=="__main__":
    main()

此实现将保持大写字母大写。

于 2012-10-18T04:10:28.410 回答
1

对于频率，常用的工具是哈希表（python 中的字典）。我对 python 不是很自信，所以我会给你一些伪代码

hashtable table
for character in string
  table[character] +=1;
list partiallySorted = alphabetize(table.keys()) 
list sortedList = stablesort partiallySorted by (table[a]<table[b] iff a<b)

稳定排序将保持相等元素之间的相对顺序，从而保留您的顺序。

幸运的是，因为 python 2.2 保证所有排序都是稳定的，所以如果你不想自己实现它，你可以调用库的 sort 函数来进行稳定排序。

于 2012-10-18T03:59:21.630 回答