分治

50 快速幂

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即）。

class Solution {
    public double myPow(double x, int n) {
    if(x==0||x==1)return x;
    if(n<0)return 1/Pow(x,-n);
    return Pow(x,n);
}
    private double Pow(double x, int n)
    {
        if(n==0)return 1;
        double y = Pow(x,n/2);
        if(n%2==0)return y*y;
        else  return y*y*x;
    }
}

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

class Solution {
    public int findKthLargest(int[] nums, int k) {
        divide(nums, 0, nums.length - 1, k);
        return nums[nums.length - k];
    }
    private void divide(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int position = conquer(nums, left, right);//代表是第几大的
        if (position == nums.length - k) {
            return;
        } else if (position < nums.length - k) {
            divide(nums, left, position + 1, k);
        } else {
            divide(nums, left, position - 1, k);
        }//确定位置与待比的位置
    }
    private int conquer(int[] nums, int left, int right) {//每一个都与墙比大小，比墙小放在左边，比墙大放在右边。
        int pivot = nums[right];
        int wall = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, wall);
                wall++;
            }
        }
        swap(nums, wall, right);
        return wall;
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}