【算法练习】leetcode算法题合集之排序篇

快速排序

单路快排

获取随机一个元素，元素左边是小于它的，元素右边是大于它的。

partition：选择一个元素，交换left。比较nums[left]和nums[i]，如果nums[i]<nums[left]，找到一个小于标的元素的数据，交换到j的位置，j记录着最后一个小于标的元素的数据，切换j和left的位置，j所在的元素就是标的元素，返回j。

获取left到right的随机一个索引，new Random().nextInt(right - left + 1) + left;。0-9随机一个数，是10的随机数。

public class QuickSort1 {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 5, 7, 4, 6};
        new QuickSort1().sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        sort(nums, left, p - 1);
        sort(nums, p + 1, right);

    }

    private int partition(int[] nums, int left, int right) {
        int p = new Random().nextInt(right - left + 1) + left;
        swap(nums, p, left);
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < nums[left]) {
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

双路快排

如果小于标的元素，符合要求，p1++；大于标的元素，符合要求，p2–。

找到前面不满足要求的元素，将前面的大的元素和后面小的元素互换位置。

选择p2：[left,p1-1]是小于标的元素的，[p2+1,right]是大于标的元素。选择p2就是选择小于标的元素的数据和标的元素互换。

public class QuickSort2 {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 5, 7, 4, 6};
        new QuickSort2().sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(nums, l, r);
        sort(nums, l, p - 1);
        sort(nums, p + 1, r);
    }

    private int partition(int[] nums, int l, int r) {
        int p = new Random().nextInt(r - l + 1) + l;
        swap(nums, l, p);
        int p1 = l + 1;
        int p2 = r;
        while (true) {
            //3  145672
            while (p1 <= p2 && nums[p1] < nums[l]) {
                p1++;

            }
            while (p1 <= p2 && nums[p2] > nums[l]) {
                p2--;

            }
            if (p1 >= p2) {
                break;
            }
            swap(nums, p1++, p2--);
        }
        swap(nums, l, p2);
        return p2;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

堆排序

用数组存储完全二叉树，parent(i)=(i-1)/2；左孩子是2*i+1，右孩子是2*1+2。

构建大顶堆。找到所有有左孩子或者有孩子的节点（0-len / 2 - 1）,和它的左孩子、右孩子比较，将大的元素切换到根节点。继续处理以小的元素为根节点的子树。

把大顶堆的最大元素放在数组最后，将数组之前的元素重新构建大顶堆。

public class HeapSort {

    public void sort(int[] nums) {
        buildHeap(nums, nums.length);
        for (int i = nums.length - 1; i > 0; i--) {
            ArrayUtil.swap(nums, i, 0);
            heapify(nums, 0, i);
        }
    }

    private void buildHeap(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
    }

    private void heapify(int[] nums, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < len && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < len && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            ArrayUtil.swap(nums, i, largest);
            heapify(nums, largest, len);
        }
    }

}

算法题

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

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

快排的解法

数组中存在两个相同元素，互换之后，i和j是满足条件的，互换之后要更新i和j的值。

快排之后，保证了j位置的元素nums[j]<=x，如果有存在小于x的元素，没有就是r+1。

class Solution_LC215 {
    public int findKthLargest(int[] nums, int k) {

        return quickFind(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickFind(int[] nums, int l, int r, int index) {
        if (l == r) return nums[index];
        int x = nums[l], i = l-1, j = r+1;
        while (i < j) {
            do {
                i++;
            } while (nums[i] < x);
            do {
                j--;
            } while (nums[j] > x);

            if (i < j) {
               swap(nums,i,j);
            }
        }

        if (index <= j) return quickFind(nums, l, j, index);
        else return quickFind(nums, j + 1, r, index);


    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

堆排序的处理思路

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        buildHeap(nums, n);
        for (int i = n - 1; i >= n - k + 1; i--) {
            swap(nums, i, 0);
            heapify(nums, 0, i);
        }
        return nums[0];
    }

    private void buildHeap(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
    }

        private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void heapify(int[] nums, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < len && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < len && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(nums, i, largest);
            heapify(nums, largest, len);
        }
    }
}

面试题 17.14. 最小K个数

面试题 17.14. 最小K个数

使用优先队列，优先队列默认是小顶堆。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int num : arr) {
            priorityQueue.add(num);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }
}

使用单路快排

class Solution {
    public int[] smallestK(int[] arr, int k) {
        qSort(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private void qSort(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r, k);
        if (p == k) {
            return;
        } else if (p < k) {
            qSort(arr, p + 1, r, k);
        } else {
            qSort(arr, l, p - 1, k);
        }
    }

    private int partition(int[] arr, int l, int r, int k) {
        int pos = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, pos);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < arr[l]) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, j, l);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

使用双路快排， j--;必须要在i++前面。因为最后获取的值是i，i满足arr[i] <= x。i从数组最前面寻找大的元素，j从数组最后面寻找小的元素，当j和i相遇，j每一次都是先走的，走的位置就是小于i的位置。如果先走i++，后走j--，获取的就是j。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        qSort(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private void qSort(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, pos);
        int x = arr[l];
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= x) {
                j--;
            }
            while (i < j && arr[i] <= x) {
                i++;
            }
            swap(arr, i, j);

        }
        swap(arr, i, l);
        if (i == k) {
            return;
        } else if (i < k) {
            qSort(arr, i + 1, r, k);
        } else {
            qSort(arr, l, i - 1, k);
        }
    }

    private int partition(int[] arr, int l, int r, int k) {
        int pos = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, pos);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < arr[l]) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, j, l);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leetcode347. 前 K 个高频元素

Leetcode347. 前 K 个高频元素

使用优先队列，存入数组，排序按照数组中每个元素的第二个数字排序。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            priorityQueue.add(new int[] { entry.getKey(), entry.getValue() });
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll()[0];
        }
        return res;
    }
}

LCR 164. 破解闯关密码

LCR 164. 破解闯关密码

使用优先队列

class Solution {
    public String crackPassword(int[] password) {
        PriorityQueue<String> priorityQueue = new PriorityQueue<>((a, b) -> {
            return (a + b).compareTo(b + a);
        });
        for (int num : password) {
            priorityQueue.add(num + "");
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!priorityQueue.isEmpty()) {
            stringBuilder.append(priorityQueue.poll());
        }
        return stringBuilder.toString();
    }
}

使用快排

找到比strings[l]小的元素，判断如果比strings[l]大的话，进行j--。

class Solution {
    public String crackPassword(int[] password) {
        String[] pwd = new String[password.length];
        for (int i = 0; i < password.length; i++) {
            pwd[i] = String.valueOf(password[i]);
        }
        quickSort(pwd, 0, password.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pwd.length; i++) {
            sb.append(pwd[i]);
        }
        return sb.toString();
    }

    private void quickSort(String[] strings, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l, j = r;
        String tmp = strings[l];
        while (i < j) {
            while (i < j && (tmp + strings[j]).compareTo(strings[j] + tmp) <= 0) {
                j--;
            }
            while (i < j && (tmp + strings[i]).compareTo(strings[i] + tmp) >= 0) {
                i++;
            }
            swap(strings, i, j);

        }
        swap(strings, i, l);
        quickSort(strings, i + 1, r);
        quickSort(strings, l, i - 1);
    }

    public void swap(String[] strs, int i, int j) {
        String tmp = strs[i];
        strs[i] = strs[j];
        strs[j] = tmp;
    }
}

Leetcode179. 最大数

Leetcode179. 最大数

和上一题一样，需要判断第一个字符是否为0。

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (a, b) -> {
            return (b + a).compareTo(a + b);
        });
        if (strs[0].equals("0"))
            return "0";
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }
}

LeetCode148: 排序链表