@Yano 2015-12-30T03:26:29.000000Z 字数 5866 阅读 5714

# LeetCode之Sort题目汇总

LeetCode

LeetCode 题目汇总

# 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.

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]

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)) {            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.

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) 的时间复杂度，归并排序最好，因为它不会因为输入序列的基本有序而变化。

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.

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;        // 统计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;    }  • 私有
• 公开
• 删除