快速排序、快速选择算法、找最近公共祖先

快速排序(用i和j双指针,左部分值小,当i=j时,两部分按基准值已经排序好,将基准值放到j即可。

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }
    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);
    }
    int partition(int[] nums,int left,int right){
        int privot=nums[left];//选第一个为基准值
        int i=left+1,j=right;
        while(i<=j){
            while(i<right&&nums[i]<=privot){// num【i如果小于基准值,i继续遍历
                i++;
            }
            while(j>left&&nums[j]>privot){
                j--;
            }
            if(i>=j) break;
            swap(nums,i,j);//跳出循环时,代表num[i]大于privot或 j小于privot
        }
        swap(nums,left,j);
        return j;
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

快速选择算法(快速排序相当于一次只排一个元素在中间,切索引值为p

     

class Solution {
    Random random=new Random();
    public int findKthLargest(int[] nums, int k) {
        k=nums.length-k;//变为求索引
        shuffle(nums);//洗牌算法
        int left=0,right=nums.length-1;
        while(left<=right){
            int p=partition(nums,left,right);
            if(k>p){
                left=p+1;//对右端的再不断分割 排序
            }else if(k<p){
                right=p-1;
            }else return nums[p];
        }
        return -1;
    }
    void shuffle(int[] nums){
        for(int i=nums.length-1;i>0;i--){
            int j=random.nextInt(i+1);//取i之前的数
            swap(nums,i,j);
        }
    }
    int partition(int nums[],int left,int right){
        int privot=nums[left];//第一个为基准值
        int i=left+1,j=right;
        while(i<=j){
            while(i<=right&&nums[i]<=privot){
            i++;
        }
        while(j>=left+1&&nums[j]>privot){
            j--;
        }
        if(i>=j) break;
        swap(nums,i,j);
        }
        swap(nums,left,j);
        return j;
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

最近公共祖先

 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root,p,q);
    }
    TreeNode find(TreeNode root,TreeNode p,TreeNode q){//用后序遍历找最近公共祖先
        if(root==null) return null;
        if(root.val==p.val||root.val==q.val){
            return root;
        }
        TreeNode left=find(root.left,p,q);
        TreeNode right=find(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        return left==null? right:left;
    }
}

相关推荐

  1. 最近公共祖先(LCA)主要算法

    2024-07-21 23:28:03       50 阅读
  2. 最近公共祖先(lca)倍增算法【模板】

    2024-07-21 23:28:03       52 阅读
  3. 最近公共祖先(LCA)

    2024-07-21 23:28:03       42 阅读
  4. 排序算法——快速排序

    2024-07-21 23:28:03       65 阅读
  5. 排序算法——快速排序

    2024-07-21 23:28:03       67 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 23:28:03       103 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 23:28:03       114 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 23:28:03       93 阅读
  4. Python语言-面向对象

    2024-07-21 23:28:03       99 阅读

热门阅读

  1. Kotlin单例、数据类、静态

    2024-07-21 23:28:03       29 阅读
  2. CSP-J模拟赛day1

    2024-07-21 23:28:03       29 阅读
  3. Linux下双网卡NAT组网

    2024-07-21 23:28:03       29 阅读
  4. Node的API基础

    2024-07-21 23:28:03       27 阅读
  5. C2W3.LAB.N-grams+Language Model+OOV

    2024-07-21 23:28:03       25 阅读
  6. 力扣题解(一和零)

    2024-07-21 23:28:03       35 阅读
  7. urllib&requests

    2024-07-21 23:28:03       26 阅读
  8. 接到需求后的开发步骤

    2024-07-21 23:28:03       30 阅读
  9. C#WPF九宫格图片背景实例

    2024-07-21 23:28:03       31 阅读
  10. 算法学习4——动态规划

    2024-07-21 23:28:03       28 阅读