笔试面试题-寻找Coder

请设计一个高效算法，再给定的字符串数组中，找到包含"Coder"的字符串(不区分大小写)，并将其作为一个新的数组返回。结果字符串的顺序按照"Coder"出现的次数递减排列，若两个串中"Coder"出现的次数相同，则保持他们在原数组中的位置关系。

给定一个字符串数组A和它的大小n，请返回结果数组。保证原数组大小小于等于300,其中每个串的长度小于等于200。同时保证一定存在包含coder的字符串。

测试样例：

["i am a coder","Coder Coder","Code"],3

返回：["Coder Coder","i am a coder"]


思路：
1、新建类Record记录输入的String数组的下标和出现coder的次数。
2、对Record进行降序排序(按照count来比较)。
3、遍历排序后的Record，根据对象保存的index找到对应的String内容，依次填入结果数组。

时间复杂度是O(n*lgn),空间复杂度是O(n)。

import java.util.*;

public class Coder {
    //实现Comparable接口，可以利用Arrays.sort()进行自动排序
    class Record implements Comparable<Record>{
        private int index;
        private int count;
        
        Record(int index,int count){
            this.index=index;
            this.count=count;
        }
        //题目要求为降序，所以将二者的位置颠倒了
        public int compareTo(Record o2){
            return o2.getCount()-count;
        }
        
        public int getIndex(){
            return index;
        }
            
        public int getCount(){
            return count;
        }
    }
    
    public String[] findCoder(String[] A, int n) {
        Record[] record=new Record[n];
        for(int i=0;i<n;i++){
            record[i]=new Record(i,countCoder(A[i]));
        }
        Arrays.sort(record);
        String[]result=new String[n];
         for(int i=0;i<n;i++){
            result[i]=A[record[i].getIndex()];
        }
        return result;
        
    }
    
    private int countCoder(String str){
        int count=0;
        str=str.toLowerCase();
        int index=0;
        while((index=str.indexOf("coder",index))!=-1){
            index+=5;
            count++;
        }
        return count;
    }
    
}