算法|排序

148. 排序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode mergerList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null){
            if (l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
            } else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        } 
        if (pre != null) pre.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return mergerList(l1, l2);
    }
}

179. 最大数

class Solution {
    private void swap(String[] strs, int i, int j) {
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
    private int commpare(String o1, String o2) {
        String str1 = o1 + o2;
        String str2 = o2 + o1;
        return str1.compareTo(str2);
    }
    private int partion(String[] strs, int left, int right) {
        String pv = strs[right];
        int j = left;
        for (int i = left; i < right; i++){
            if (commpare(strs[i], pv) < 0) {
                swap(strs, j, i);
                j++;
            }
        }
        swap(strs, j, right);
        return j;
    }
    private void quickSort(String[] strs, int left, int right) {
        if (left >= right) return;
        int pi = partion(strs, left, right);
        quickSort(strs, left, pi - 1);
        quickSort(strs, pi + 1, right);
    }
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++){
            strs[i] = nums[i] + "";
        }
        
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) {
            res.append(strs[i]);
        }
        String result = res.toString();
        if (result.charAt(0) == '0') result = "0";
        return result;
    }
}

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = nums[i] + "";
        }
        Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        StringBuilder res = new StringBuilder();
        for (String str:strs){
            res.append(str);
        }
        String result = res.toString();
        if (result.charAt(0) == '0') result = "0";
        return result;

    }
}

215. 数组中的第K个最大元素

class Solution {
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private int partition(int[] nums, int left, int right) {
        Random random = new Random();
        int ranIndex = random.nextInt(right - left + 1) + left;
        swap(nums, ranIndex, right);
        int pv = nums[right];
        int j = left;
        for (int i = left; i < right; i++){
            if (nums[i] < pv) {
                swap(nums, i, j);
                j++;
            }
        }
        swap(nums, j, right);
        return j;
    }
    private int findKthLargest(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        if (left > right) return -1;
        int pi = partition(nums, left, right);
        if (pi == k) return nums[pi];
        else if (pi > k) return findKthLargest(nums, left, pi - 1, k);
        else return findKthLargest(nums, pi + 1, right, k);
    }
    public int findKthLargest(int[] nums, int k) {
        int length = nums.length;
        return findKthLargest(nums, 0,length - 1, length - k);
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o1 - o2);
        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.poll();
    }
}

class Solution {
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private int partition(int[] nums, int left, int rigth) {
        Random random = new Random();
        int ranIndex = random.nextInt(rigth - left + 1) + left;
        swap(nums, ranIndex, left);
        int pv = nums[left];
        int i = left; 
        int j = rigth;
        while (i < j) {
            while (i < j && nums[j] > pv) {
                j--;
            }
            while (i < j && nums[i] <= pv) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, left, i);
        return i;   
    }
    private int findKthLargest(int[] nums, int left, int rigth, int k) {
        if (left == rigth) return nums[left];
        if (left > rigth) return -1;
        int pi = partition(nums, left, rigth);
        if (pi == k) return nums[pi];
        else if (pi > k) return findKthLargest(nums, left, pi - 1, k);
        else return findKthLargest(nums, pi + 1, rigth, k);
        
    }
    public int findKthLargest(int[] nums, int k) {
        int length = nums.length;
        return findKthLargest(nums, 0, length - 1, length - k);
    }
}

347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
        }
        //最小堆
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)->o1[1] - o2[1]);
        for (Map.Entry<Integer, Integer> entry:hashMap.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            queue.offer(new int[]{key, value});
            if (queue.size() > k) queue.poll();
        }
        int[] result = new int[k];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}

class Solution {
    private void swap(ArrayList<int[]> list, int i, int j) {
        int[] temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
    private int partition(ArrayList<int[]> list, int left, int rigth) {
        Random random = new Random();
        int ranIndex = random.nextInt(rigth - left + 1) + left;
        swap(list, ranIndex, rigth);
        int pv = list.get(rigth)[1];
        int j = left;
        for (int i = left; i < rigth; i++){
            if (list.get(i)[1] < pv) {
                swap(list, i, j);
                j++;
            }
        }
        swap(list, j, rigth);
        return j;
    }
    private int[] topKFrequent(ArrayList<int[]> list, int left, int rigth, int k) {
        if (left == rigth) {
            int[] result = new int[list.size() - k];
            for (int i = 0; i < result.length; i++) {
                result[i] = list.get(left + i)[0];
            }

            return result;
        }
        int pi = partition(list, left, rigth);
        if (pi == k) {
            int[] result = new int[list.size() - k];
            // System.out.println(result.length);
            for (int i = 0; i < result.length; i++) {
                result[i] = list.get(pi  + i)[0];
            }
            return result;
        } else if (pi > k) return topKFrequent(list, left, pi - 1, k);
        else return topKFrequent(list, pi + 1, rigth, k);
    }
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
        }
        ArrayList<int[]> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry:hashMap.entrySet()) {
            list.add(new int[]{entry.getKey(), entry.getValue()});
            // System.out.println(entry.getKey() + " " + entry.getValue());
        }
        int length = list.size();
        return topKFrequent(list, 0, length - 1, length - k);
    }
}

面试题45. 把数组排成最小的数

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < strs.length; i++) {
            strs[i] = nums[i] + "";
        }
        Arrays.sort(strs, (o1, o2)->(o1 + o2).compareTo(o2 + o1));
        StringBuilder res = new StringBuilder();
        for (String str:strs) {
            res.append(str);
        }
        String result = res.toString();
        // if (result.charAt(0) == '0') result = "0";
        return result;
    }
}