signed

QiShunwang

“诚信为本、客户至上”

算法岗面试题目总结

2021/5/14 22:11:15   来源:

仅以这几篇博文记录我的秋招之路

算法岗面试题目总结

一、 面试高频问题:排序(O(1) 复杂度的归并,堆排序,快速排序)
1.归并排序

//空间复杂度O(1),时间复杂度o(nlogn)
    public static void main(String[] args) {
        int[] arr = new int[]{14,12,15,13,11,16};
        //找到数组的最大值,并计算出maxval,然后调用递归的归并排序
        int maxval = Arrays.stream(arr).max().getAsInt() + 1;
        mergeSortDigui(arr, 0, arr.length - 1, maxval);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    // 递归归并排序
    public static void mergeSortDigui(int[] nums, int l, int r,int max){
        if(l < r){
            int mid = l + (r - l)/2;
            mergeSortDigui(nums,l, mid,max);
            mergeSortDigui(nums, mid + 1, r,max);
            mergeSortO1(nums, l, mid, r, max);
        }
    }

    //O(1)复杂度
    //用两个数来存储一个数
    public static void mergeSortO1(int[] arr, int l, int mid, int r, int max) {
        int start0 = l, start1 = mid+1, i = l;
        while(start0 <= mid && start1 <= r){
            if(arr[start0] % max <= arr[start1] % max){
                arr[i] = arr[i] + (arr[start0] % max) *max;
                i++;
                start0++;
            }
            else {
                arr[i] = arr[i] + (arr[start1] % max ) *max;
                i++;
                start1++;
            }
        }
        while (start0 <= mid){
            arr[i] = arr[i] + (arr[start0] % max) *max;
            i++;
            start0++;
        }
        while (start1 <= r){
            arr[i] = arr[i] + (arr[start1] % max ) *max;
            i++;
            start1++;
        }
        for(start0 = l; start0 <= r; start0++)
            arr[start0] = arr[start0] /max;
    }

2、快速排序

public static void main(String[] args) {
        int[] nums = new int[]{5,3,8,6,4};
        quickSort(nums, 0, nums.length-1);
    }
    public static void quickSort(int[] nums, int l, int r){
        if(l >= r) return;
        int base = nums[l], i = l, j = r;
        while (i < j){
            while (i < j && nums[j] > base)
                j--;
            if(i < j)
                nums[i++] = nums[j];
            while (i < r && nums[i] < base)
                i++;
            if(i < r)
                nums[j--] = nums[i];
        }
        nums[i] = base;
        quickSort(nums, l, i-1);
        quickSort(nums, i+1, r);
    }

3、堆排序

public static void main(String[] args) {
        int[] nums = new int[]{14,12,15,13,11,16};
        heapSort(nums);
    }
    //堆排序空间复杂度O(1),时间复杂度o(nlogn)
    public static void heapSort(int[] arr) {
        for(int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for(int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);
            adjustHeap(arr, 0, j);
        }
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//先取出当前元素i
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,也就是2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }