算法-每天一道题（13）-寻找Coder

请设计一个高效算法，再给定的字符串数组中，找到包含”Coder”的字符串(不区分大小写)，并将其作为一个新的数组返回。结果字符串的顺序按照”Coder”出现的次数递减排列，若两个串中”Coder”出现的次数相同，则保持他们在原数组中的位置关系。给定一个字符串数组A和它的大小n，请返回结果数组。保证原数组大小小于等于300,其中每个串的长度小于等于200。同时保证一定存在包含coder的字符串。

测试样例：

[“i am a coder”,”Coder Coder”,”Code”],3

返回：

[“Coder Coder”,”i am a coder”]

Python

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

import re
class Coder:
    def findCoder(self, A, n):
        # write code here
        result = [] # 新列表存放A中对应的coder数，即A[i]中coder数=result[i]
        p = re.compile("coder", re.I)
        for A_item in A:
            p_items = p.findall(A_item)
            result.append(len(p_items))
            
        # 上面的正则循环，已经把对应的数目得到了，再进行排序就可以了
        # 不能使用冒泡等排序，因为冒泡排序可能会改变值的index
        # 这里排序的思路：找到[0,n]最大的，保存起来，删除，再在末尾追加该值
        # 第二次循环的时候，就应该找[0,n-1]，第三次[0,n-2]以此类推
        length = n
        for i in xrange(0, n):
            max_index = result.index(max(result[:length]))
            length = length - 1
            
            result_temp = result[max_index]
            A_temp = A[max_index]

            del result[max_index]
            del A[max_index]
            
            # 如果是0(即没有coder的时候)，就删除不追加，不能使用break，因为还存在其他的0
            if result_temp == 0:
                continue
            else:
            	result.append(result_temp)
            	A.append(A_temp)
                
        return A

'''
解题思路：

与其说是查找，还不是说排序算法，设计一种不会改变元素位置的排序算法
其实这里的这个排序效率比较低下
'''