leetcode排序总结

96 阅读 0 评论 64 点赞

我是靠谱客的博主隐形方盒，这篇文章主要介绍leetcode排序总结，现在分享给大家，希望可以做个参考。

leetcode上的排序题大多基于排序的应用，几乎不涉及对经典排序算法的实现，类似147链表插入排序。下面就对排序算法稍微做一点总结。

排序分为基于比较的排序和非比较排序。

比较排序主要有：冒泡排序，选择排序，插入排序（基于二分查找的插入排序/希尔排序（分组插入排序）），归并排序，堆排序，快速排序。

希尔排序利用了在待排记录基本有序，直接插入排序效率增加的特性，取大步长将全部元素分成几个区域分别进行插入排序，再取越来越小的步长进行排序，此时需排序数据基本有序，插入排序速度较快。

归并排序的递归实现本质上是分支策略的典型应用，分解，求解，组合。

非递归实现是两两归并，四四归并，八八归并...

堆排序利用堆数据结构设计的一种选择排序算法，待排序记录序列用完全二叉树表示（通过一维数组）过程如下

快速排序因其效率较高，在很多场合中被使用，笔面试题中也经常出现，基本实现步骤如图

另外还有填坑法快速排序

下面给出一张性能比较表格

排序算法稳定性的简单形式化定义为：如果A_i = A_j，排序前A_i在A_j之前，排序后A_i还在A_j之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。即如果需求需保持初始的排序，那么稳定性排序将有意义。

常用排序算法总结这篇博客写的比较详细，推荐一看

75. Sort Colors

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

复制代码

1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

思考一趟扫描算法，即需每次遇到0都交换到前面，每次遇到2都交换到后面，所以需三个指针记录首尾及当前

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void sortColors(int[] nums) {
        int start=0;
        int end = nums.length-1;
        int current=0;
        while(current<=end) {
            if(nums[current]==0) {
                nums[current]=nums[start];  //start处值交换到current处
                nums[start]=0; //start处为0
                start++;
                current++; //current只可能跟start一起移动或start把1交换过来
            } else if(nums[current]==2) {
                nums[current]=nums[end];
                nums[end]=2;
                end--;
            } else {
                current++;  //等于1时不处理
            }
        }
    }

179. Largest Number

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

复制代码

1
2
输入: [10,2]
输出: 210

示例 2:

复制代码

1
2
输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

实现一个比较接口，对数组进行从大到小的排序，而int数组不能直接实现接口Comparator<int>，且最后输出的是拼接字符串，索性把int数组转为String数组处理。开始实现两字符串比较函数是想通过将其拆分然后按位比，但实际上String已经实现了一个compareTo，按字典序比较。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String largestNumber(int[] nums) {
        String[] strarr = new String[nums.length];
        for(int i=0;i<nums.length;i++)
            strarr[i] = String.valueOf(nums[i]);

        Arrays.sort(strarr, new Comparator<String>(){
            @Override
            public int compare(String str1, String str2) {
                String order1 = str1+str2;
                String order2 = str2+str1;
                return order2.compareTo(order1);
            }
        });
        
        if(strarr[0].equals("0"))
            return "0";
        
        String ret = "";
        for(int i=0;i<strarr.length;i++) 
            ret+=strarr[i];
        return ret;
    }

274. H-Index

给定一位研究者的论文被引用次数的数组（被引用次数是非负整数）。写一个方法计算出研究者的H指数。

H-index定义: “一位科学家有指数 h 是指他（她）的 N 篇论文中至多有 h 篇论文，分别被引用了至少 h 次，其余的 N - h 篇论文每篇被引用次数不多于 h 次。"

例如，给定 citations = [3, 0, 6, 1, 5]，意味着研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以他的 h 指数是 3。

注意： 如果 h有几个可能的值， h 指数是指其中最大的那个。

至此遇到了瓜子的全部两道编程题...这道题目比较简单，先将数组排序，再从后向前比较即可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h=0;
        for(int i=citations.length-1;i>=0;i--) {
            if(citations[i]>=h+1)
                h++;
            else
                break;
        }
        return h;
    }

524. Longest Word in Dictionary through Deleting

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

复制代码

1
2
3
4
5
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

示例 2:

复制代码

1
2
3
4
5
输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

说明:

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

每一个字符串与目标字符串逐个字符比较，通过比较当前串与当前最大串的长度及字典序对列表中字符串进行剪枝，减小比较次数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String findLongestWord(String s, List<String> d) {
        char[] sarr = s.toCharArray();
        String maxstring = "";
        for(int i=0;i<d.size();i++) {
            String tmp = d.get(i);
            //长度相等，字典序小或长度大与当前最大值则进行比较
            if((tmp.length()==maxstring.length()&&tmp.compareTo(maxstring)<0)||tmp.length()>maxstring.length()) {
                int j=0,k=0;
                char[] darr = tmp.toCharArray();
                while(j<s.length()) {
                    if(sarr[j]==darr[k]) {
                        k++;
                    }
                    if(k==tmp.length()){
                        maxstring=tmp;
                        break;
                    }
                    j++;
                }
            }
        }
        return maxstring;
    }

56. Merge Intervals

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

复制代码

1
2
3
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

复制代码

1
2
3
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

将数组按start大小排序，后逐个对区间进行处理，该合并处合并

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals,new Comparator<Interval>() {
            public int compare(Interval int1,Interval int2) {
                return int1.start-int2.start;
            }
        });
        int i=0;
        while(i<intervals.size()-1) {
            Interval merge1=intervals.get(i);
            Interval merge2=intervals.get(i+1);
            if(merge1.end>=merge2.start) {
                intervals.get(i).end = merge1.end>merge2.end?merge1.end:merge2.end;
                intervals.remove(i+1);
            } else {
                i++;
            }
        }
        return intervals;
    }