Java 中的快排，二分查找变形系列

2019-04-20 本文已影响1人 Java极客技术

常用算法笔记

快排

经典面试算法，面试中可以说是经常被问到。实现原理，找一个基准点，两个指针，依次比较互换位置。算法实现如下：

package com.silence.arts.leetcode.second;

public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{10, 5, 3, 1, 7, 2, 8, 0};
        quickSort2(array, 0, array.length - 1);
        for (int element : array) {
            System.out.print(element + " ");
        }
    }

    public static void quickSort2(int[] arr, int left, int right) {
        if (left < right) {
            int position = position(arr, left, right);
            quickSort2(arr, left, position - 1);
            quickSort2(arr, position + 1, right);
        }
    }

    public static int position(int[] array, int left, int right) {
        int base = array[left];
        while (left < right) {
            while (right > left && array[right] >= base) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= base) {
                left++;
            }
            array[right] = array[left];

        }
        //此时 left == right
        array[left] = base;
        return left;
    }
}

二分查找变形

二分查询效率高，效果好，而且也有很多变形的方式，下面介绍几种变形

查找第一个值等于给定值的元素下标

package com.silence.arts.leetcode.binary;

public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
        System.out.println(bsearch4(a, a.length, 12));
    }

    /**
     * 变形一：二分查找变形题，查找第一个值等于给定值的元素下标
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如查找8，应该返回5
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch1(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || array[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

查找最后一个值等于给定值的元素

    /**
     * 变形二：查找最后一个值等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch2(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == n - 1 || array[mid + 1] != value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

查找第一个大于等于给定值的元素

    /**
     * 变形三：查找第一个大于等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch3(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] >= value) {
                if ((mid == 0) || (array[mid - 1] < value)) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

查找最后一个小于等于给定值的元素

    /**
     * 变形四：查找最后一个小于等于给定值的元素
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如value = 12，则应该返回11的下标8
     * System.out.println(bsearch4(a, a.length, 12));
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch4(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == n - 1 || array[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}

链表反转

链表反转也是一个非常经典的面试题，主要考察思维，常用的 Java 方式大家应该都知道，下面提供一个 Python 的方式，简单的一行代码就搞定了

人生苦短，我用 Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

题外话

一个理工男程序员，除了敲代码之外，还喜欢看书听音乐写写东西。
如果大家喜欢我的文章的话，欢迎大家转发评论点赞，你们的喜欢是对我最大的鼓励。

公众号：沙漏洒洒，主要用来分享技术和成长感悟，如果喜欢欢迎关注
博~~客：个人网站