LeetCode之Sort题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

Credits: 
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题目描述不清，实际上，H-Index的核心计算方法是：

1、将某作者的所有文章的引用频次按照从大到小的位置排列

2、从前到后，找到最后一个满足条件的位置，其条件为：此位置是数组的第x个，其值为y，必须满足 y >= x;

    public int hIndex(int[] citations) {
        if (citations == null) {
            return 0;
        }
        int h = 0, n = citations.length;
        Arrays.sort(citations);
        for (int i = n - 1; i >= 0; i--) {
            if (citations[i] >= n - i) {
                h = n - i;
            } else {
                break;
            }
        }
        return h;
    }

H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

二分查找

    public int hIndex(int[] citations) {
        int n = citations.length;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return n - low;
    }

Insertion Sort List

Sort a linked list using insertion sort.

    public ListNode insertionSortList(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return head;
        final ListNode _head = new ListNode(Integer.MIN_VALUE);
        _head.next = head;
        head = head.next;
        _head.next.next = null;
        next: while (head != null) {
            ListNode taken = head;
            head = head.next;
            ListNode cur = _head.next;
            ListNode last = _head;
            while (cur != null) {
                if (cur.val > taken.val) {
                    // insert
                    last.next = taken;
                    taken.next = cur;
                    continue next;
                }
                cur = cur.next;
                last = last.next;
            }
            last.next = taken;
            taken.next = null;
        }
        return _head.next;
    }

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

[3, 30, 34, 5, 9]
排序成……
[9, 5, 34, 3, 30]

如何判断大小？对于每个元素，左边第一位大的在前面，如5>30。因为5的第一位是5是5,30的第一位是3。依次比较。

那么3应该比30大，因为3 + 30 = 330 ，而30 + 3 = 303。

所以本题可分为4步：

1. 定义string数组，将int数组，转成string数组
2. 对string数组按照定义的规则排序
3. 如果strs第一个元素是“0”，则结果是0
4. 连接strs数组成字符串，即为结果

    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        // 将int数组，转成string数组
        for (int i = 0; i < strs.length; i++) {
            strs[i] = nums[i] + "";
        }
        // 对strs排序
        Arrays.sort(strs, new Comparator<String>() {
            public int compare(String x, String y) {
                return (y + x).compareTo(x + y);
            }
        });
        // 如果strs第一个元素是“0”，则结果是0
        if ("0".equals(strs[0])) {
            return "0";
        }
        // 连接strs数组成字符串
        return String.join("", strs);
    }

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: 
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up: 
A rather straight forward solution is a two-pass algorithm using counting sort. 
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // 定义三个变量，存储三种颜色出现次数
        int red = 0;
        int white = 0;
        int blue = 0;
        // 循环一次，记录每种颜色出现次数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                red++;
            } else if (nums[i] == 1) {
                white++;
            } else {
                blue++;
            }
        }
        // 对nums数组重新赋值
        int i = 0;
        while (red-- > 0) {
            nums[i++] = 0;
        }
        while (white-- > 0) {
            nums[i++] = 1;
        }
        while (blue-- > 0) {
            nums[i++] = 2;
        }
    }

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

O(n log n) 的时间复杂度，归并排序最好，因为它不会因为输入序列的基本有序而变化。

参考：LeetCode 021 Merge Two Sorted Lists

1. 首先将List分成两个
2. MergeSort(left) ，MegerSort(right)
3. LeetCode 021 Merge Two Sorted Lists

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode rt = new ListNode(0);
        ListNode h = rt;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                rt.next = l1;
                l1 = l1.next;
            } else {
                rt.next = l2;
                l2 = l2.next;
            }
            rt = rt.next;
        }
        if (l1 != null)
            rt.next = l1;
        else
            rt.next = l2;
        return h.next;
    }
    public ListNode sortList(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode h2 = slow.next;
        slow.next = null;
        return mergeTwoLists(sortList(head), sortList(h2));
    }

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, 
s = "anagram", t = "nagaram", return true. 
s = "rat", t = "car", return false.

Note: 
You may assume the string contains only lowercase alphabets.

Follow up: 
What if the inputs contain unicode characters? How would you adapt your solution to such case?

用数组模拟哈希表，统计字符出现次数。

    public boolean isAnagram(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }
        if (s.equals(t)) {
            return false;
        }
        int len = s.length();
        int[] map = new int[26];
        // 统计s中每个字符出现的次数
        for (int i = 0; i < len; i++) {
            map[s.charAt(i) - 'a']++;
        }
        // 减去t中相应字符出现次数
        for (int i = 0; i < len; i++) {
            map[t.charAt(i) - 'a']--;
            if (map[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (map[i] != 0) {
                return false;
            }
        }
        return true;
    }