1. 时间复杂度概述
一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,就叫做常数操作,时间复杂度为一个算法流程中,常数操作数量的一个指标,常用BigO进行表示,具体来说,需要分析出这个算法流程中所发生的常数操作的次数,最终总结出常数操作数量的表达式
在表达式中一般只取渐进上界,也就是说只要高阶项而不要低阶项。
2. 选择排序
void seleceSort(int[] arr){
if(arr == null || arr.length <2){
return ;
}
for(int i = 0;i<arr.length-1;i++){
int minIndex = i;
for(int j = i+1;j<arr.length;j++){
//在i+1~N-1找最小值的下标
minIndex = arr[j]<arr[minIndex]?j:minIndex;
}
swap(arr,i,minIndex);
}
}
void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j]=temp;
}3. 冒泡排序
冒泡排序本质上也是归位的过程,选择排序的归位的是将较小值归位,而冒泡排序是通过相邻元素之间两两比较,将比较大的元素不断向后面搬。
那么算法的流程就是:不断比较相邻的元素,如果这个元素比右边的元素要大,那么就将左边的这个元素搬到右边去.
public static void bubbleSort(int[] arr){
if(arr == null || arr.length<2){return;}
for(int e = arr.length-1;e>=0;e--){
for(int i = 0;i<e;i++){
if(arr[i]>arr[i+1]){//如果左边这个元素比右边的元素要大,那么就将左边的这个元素搬到右边去
swawp(a.i,i+1);
}
}
}
}
public static void swap(int[] arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}关于异或运算实现的交换运算复习
异或是相同为0,不同为1,异或运算从本质上理解也可以说是无进位的相加
比如说
10110
00111
----------
10001性质:
- 0与任意一个数进行异或,结果都是这个数
- 任意一个数与自己进行异或,都会得到0
- 异或运算满足交换律和结合律
- a^b^c=a^(b^c):同样一批数,与选择谁先异或或者谁后异或无关
实现两个数的交换可以用如下的代码
a = a^b;
b = a^b;
a = a^b;
//解释如下,假设a=1,b=2
a=1^2;
b=(1^2)^2=1^(2^2)=1^0=1;
a=(1^2)^1=2^0=2能够执行上述条件的前提是这两个数是在不同的内存空间中的,如果是在同一个内存空间的,那么最终就会变成0
这是因为:
//假设a=1,a和b指向的是同一块内存空间
a = 1^1;
b=a=1^1^1^1=0;
a=0;面试题
假设给你一个数组arr[],这个数组中有一种数,这个数出现了奇数次,而其他所有的数都出现了偶数次,请你找出这个数,要求时间复杂度为O(N),空间复杂度为O(1)
这道题同样可以使用的是异或的思路,其关键还是性质：
- 异或满足交换律或者结合律
- 自己和自己异或结果还是0
- 0和任何数异或都等于自己
那么我们知道,如果我们以一开始为0,遍历整个arr,对整个arr里面的数都异或一次
- 出现偶数次的数会在最终的异或完成之后变成0
- 出现奇数次的数最终会变成自身
public static int solve(int[]arr){
if(arr == null ||arr.length <2){return;}
int eor = 0;
for(int i = 0;i<n;i++){
eor = eor^arr[i];
}
return eor;
}那么到这里,必须要说明一下上述性质是为什么成立的,需要证明的是为什么异或满足交换律或者结合律
之前已经说过,异或可以看作是无进位的加法,无进位的加分只和本位上的数字有关,而无加法的顺序无关,因此是满足结合律/交换律的
进阶:如果存在两种这样的出现的奇次的数
对于这道题,如果我们采取之前的办法的话,那么最终得到的eor=a^b
那么现在的问题就是,我们如何分离出a^b?
我们知道异或的性质是相同为0,不同为1,因为是存在两种这样的数,因此这样的数肯定是互不相同的,
因此我们能够确保a和b在某些位上的肯定是不一样的,而这些不一样恰恰就保存在a^b中,假设a^b的第8位是1,那么也就说明a和b的第八位是不一样的,这时候就将arr[]中的数分成了两波
- 第八位为0的
- 第八位不为0的
然后我们让eor’只异或那些第八位为0的,就可以顺利得到a或者b其中的一个,这样就求出来了
int rigthOne = eor & (~eor+1);这个是求取一个数的最右边的1的表达式公式
- eor:就是原数
- ~eor:就是这个原数按位取反
- ~eor+1:按位取反后+1
public static void printOddNum(int[] arr){
int eor=0,onlyOne = 0;
for (int num : arr) {
eor ^= num;
}
//eor=a^b
//eor必有一个位置上是1,我们想办法找1
int rightOne = eor & (~eor+1);
//再次异或
for (int num : arr) {
//如果那一位是1
if((num&rightOne) != 0){
onlyOne ^= num;
}
}
System.out.println(onlyOne+" "+(onlyOne^eor));
}4. 插入排序
插入排序的本质是让区间有序,在区间有序的基础进行排序
public static void insertSort(int[] arr){
if(arr == null || arr.length <2){
return;
}
//对0...n之间的区间做到有序
//1.0~0是有序的
//2.0~i打算排成有序
for(int i = 1;i<arr.length;i++){
for(int j = i-1;j>=0&&arr[j]>arr[j+1];j--){
swap(arr,j,j+1);
}
}
} 二分插入排序优化
public static void insertSort(int[] arr){
//插入排序
if(arr == null || arr.length <2){
return;
}
for(int i = 1;i<arr.length;i++){
for(int j = i-1;j>=0&&arr[j]>arr[j+1];j--){
swap(arr,j,j+1);
}
}
}
//二分搜索查找
public static void binaryInsertSort(int[] arr){
if(arr == null || arr.length <2){
return;
}
//已知0-i-1是有序的
for(int i = 1;i<arr.length;i++){//对于a[i],在0-i-1的位置上寻找合适的位置
//首先比较是否能够形成有序的的数组
if(arr[i]>=arr[i-1]){continue;}
//否则的话就是不能,需要寻找合适的位置,一个个换位置
//定义搜索区间[0,i-1]
int temp = arr[i];
int left = 0,right = i-1;
int mostLeft = -1;
while (left <= right){
int mid = left+(right-left)/2;
if(arr[mid]<arr[i]){
//找到arr[i]所在的位置
//这个位置可以进行如下定义:是大于等于arr[i]的最左侧的位置
left = mid+1;
mostLeft = left;
}else{
right = mid-1;
}
}
//然后对这个mostLeft之前的位置向右挪
for(int j = i;j>mostLeft;j--){
arr[j] = arr[j-1];
}
arr[mostLeft] =temp;
}
}5. 递归概述
面试题:用递归的方法求一个数组中的最大值
可以用二分搜索的办法,我们知道数组的最大值肯定是分成这两半的数组中,这两个数组的最大值取再大得到的,因此我们可以这样定义递归函数,getMax(arr,L,R):int,表示返回从[L,R]上的最大值
public int getMax(int[] arr,int l,int r){
if(l == r){
return arr[l];//base-case,最大值就是它自己
}
int mid = l+((l+r)<<1);
int lMax = getMax(arr,l,mid);
int rMax = getMax(arr,mid+1,r);
return Math.max(lMax,rMax);
}
psvm{
int max = getMax(arr,0,arr.length-1);
}使用master公式估算递归的时间复杂度
T(n) = a*T(N/b)+O(N^d)
- T(N):母问题的数据规模是N
- N/b:代表在这个母问题拆解的过程,所拆解而成的子问题的规模大小,注意,这里要是等量的
- a:计算子问题的次数
- N^d:除了求解子问题之外的额外过程
关于额外过程的时间复杂度
- 当logba<d的时候,此时为O(N^d)
- 当logba>d的时候,此时为O(N^(logba))
- 当loba==d的时候,此时O(N^d*logN)
谁大取谁,相等相乘
6. 归并排序
- 简单递归,让左边排好序,右边排好序,让其整体有序
- 让其整体有序的过程中用了外排序的办法
假设有一个数组[L,R],假设其中点是mid,那么要做的就是让[L,mid]有序,让[mid+1,R]有序,最后让这部分整合在一起有序,最终[L,R]就是有序的
合并[L,mid]和[mid+1,R]的过程如下:
创建两个指针l和r,其中l指向L,r指向mid+1,再创建结果数组res[]
如果nums[l]<=nums[r],res[k] = nums[l]
否则res[k] = nums[r]
当k == R-L的时候,这时候合并结束
特殊情况:
当l==mid&&r!=R时,此时只需要将[r,R]上的数字全部拷贝到数组res即可
当l!=mid&&r==R时,此时只需要将[l,mid]上的数字全部拷贝到数组res即可
//让[L,R]上的数有序
public static void process(int[] nums,int L,int R){
if(L>R){return;}
if(L==R){return ;}//base-case
int mid = L+((R-L)>>1);
process(nums,L,mid);//让左边这部分有序
process(nums,mid+1,R);//让右边这部分有序
merge(nums,L,mid,R);
}
//双指针方法
public static void merge(int[] nums,int l,int mid,int r){
int[] help = new int[r-l+1];
int k = 0;
int p1 = l;
int p2 = mid+1;
while (p1<=mid && p2<=r){
if(nums[p1]<=nums[p2]){
help[k++]=nums[p1++];
}else {
help[k++] = nums[p2++];
}
}
while (p1<=mid){
help[k++] = nums[p1++];
}
while (p2<=r){
help[k++]=nums[p2++];
}
//然后将数组的值填到nums
System.arraycopy(help, 0, nums, l, help.length);
}分析时间复杂度,从主过程开始,主过程下含有两个等规模大小的子过程,也就是
T(N)=2T(N/2)
而额外的过程是O(N)的,因为只对L,R上的数字只做一次操作
T(N)=2T(N/2)+O(N)
此时a=2,b=2,d=1
此时logab=1,根据谁大取大,相等相乘的原则,因此时间复杂度为O(NlogN)
面试题:小和问题
在一个数组中,每一个数左边比当前数小的数累加起来,所有的和就叫做这个数组的小和
正着想:如果想要求小和,那么就是求每一个位置i左边比它小的数的和
反着想:从产生小和的过程中来思考,如果我左边的这个数比右边的那个数要小,那么在最终计算小和的时候,左边的这个数就会算进小和里面去,那么也可以变成:
求我当前右边的数比我当前要大的数的个数*当前这个数,就等于当前这数所产生的小和
那么这个过程就可以用归并排序的过程来做,为什么呢?我们先来回忆一下归并排序的过程:
它首先是做了一个分段,这个分段分成了两个部分,左部和右部,在这个左部和右部中,左部的元素与右部的元素是严格隔离的,无论其内部如何做排序,左部和右部的左右关系都是在这一个阶段不会变化的(指的是左部的元素肯定是在右部的元素的左边)
和归并排序有什么关系呢?
归并排序的过程能够产生两个段,这两个段中有着严格的大小关系。
在递归的最低层,会进入到一个base-case,L==R,这时候不会产生小和,而且在这个阶段,已经将整个数组分成了若干个小段,这些若干个小段,也是相互隔离的,不会产生影响相互次序的关系。
关键问题:排序是否会影响左右两边元素的次序
这个问题是比较值得担心的,因为每次的排序过程都会改变数组的次序,但是不改变数组的次序的话,那么就会增多一次O(n)的遍历,退化为n方的算法,因此这个问题必须要搞懂,我们在归并排序的过程中,每次都会进行一个划分-合并的递归操作,其中划分的操作产生了相互隔离的一小段,而合并的操作,在即将要合并之前,也会产生相互隔离的一小段,而这些相互隔离的一小段,都不会影响互相的次序,因此我们必须在这个阶段进行小和的计算,这样的话才能确保不会影响相互的次序而影响答案。
关键问题:有没有可能漏解,或者多解?
- 漏解:不可能漏解,我们从递归的最底层开始分析,当递归到最底层的时候,这时候每个元素单独占一段,每个元素都会被计算,不会导致有元素遗漏
- 多解:不可能多解,我们从局部状态和全局状态分析
- 局部状态:对于局部状态而言,其与其他元素的小和计算次数只会有一次,这是因为分段是隔离的,单次的。
- 全局状态:对于全局状态而言,其余整个数组的元素的小和计算次数有且只有一次,这也是因为分段是隔离的
关键问题:什么时候会产生小和?
只要在进行有关元素的比较的时候都会产生小和
- process:进行归并排序的时候,两个局部内部产生的小和
- merge:进行归并的时候,两个局部之间所产生的小和
//让[L,R]上的数有序
public static int process(int[] nums,int L,int R){
if(L>R){return 0;}
if(L==R){return 0;}//base-case
int mid = L+((R-L)>>1);
return process(nums,L,mid)+
process(nums,mid+1,R)+
merge(nums,L,mid,R);
}
//双指针方法
public static int merge(int[] nums,int l,int mid,int r){
int[] help = new int[r-l+1];
int k = 0;
int p1 = l;
int p2 = mid+1;
int res = 0;
while (p1<=mid && p2<=r){
if(nums[p1]<nums[p2]){//左边的数比右边的数要小(严格这样定义,因为等于的话不会产生小和),那么就会产生小和
res += (r-p2+1)*nums[p1];
help[k++]=nums[p1++];
}else {
help[k++] = nums[p2++];
}
}
while (p1<=mid){
help[k++] = nums[p1++];
}
while (p2<=r){
help[k++]=nums[p2++];
}
//然后将数组的值填到nums
System.arraycopy(help, 0, nums, l, help.length);
return res;
}面试题: 计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
这道题和小和问十分类似,也可以利用归并排序进行求解,而基本原理还是:
在归并排序中,被二分的子数组间的左右位置关系不会改变
比如说
1 2 3 4->1 2、3 4那么在merge中
1必定是在3的左边,实现了数组间的隔离,至于多解和漏解问题的话看上面的分析
那么关键是:统计当前这个数,它右边小于当前元素的个数
假设我们通过二分,将数组分成了两部分[lo,mid]和[mid+1,hi]
然后执行merge(),使用双指针法i指向lo,j指向mid+1
如果我们发现nums[i]<=nums[j]
那么也就是说,[mid+1,j)的这一段都是小于当前元素的,那么我们只需要统计这一段就可以了
那么有几个元素呢?我们以区间计算[mid+1,j-1],也就是(j-1-mid-1)+1= j-mid-1
公式:闭区间内的元素格式 = 右边-左边+1
于是我们发现了计算的时机
- 首先第一个,比较
temp[i]和temp[j]的时候,当temp[i]<=temp[j]的时候,可以计算 - 第二个,我们知道
merge()的时候,都是先将小的数放到原数组里面去的,如果出现了j == hi+1,那么就说明,这时候左边的数组中剩余未归位的元素比右边区间内的所有元素都要大,可以计算
AC代码如下以及代码实现细节如下:
class Solution {
//由于在计算过程中会对数组进行排序,因此需要记录下原数组的下标
private class Pair{
public int val;
public int index;
}
private Pair[] memo;
private int[] count;
public List<Integer> countSmaller(int[] nums) {
memo = new Pair[nums.length];
count = new int[nums.length];
Pair[] nums2 = new Pair[nums.length];
for(int i = 0;i< nums.length;i++){
nums2[i] = new Pair();
nums2[i].val = nums[i];
nums2[i].index = i;
}
sort(nums2,0, nums2.length-1);
List<Integer> list = new ArrayList<>(nums.length);
for (int number : count) {
list.add(number);
}
return list;
}
private void sort(Pair[] nums,int lo,int hi){
if(lo == hi){
return;
}
//后序遍历
int mid = lo + ((hi - lo)/2);
sort(nums,lo,mid);
sort(nums,mid+1,hi);
merge(nums,lo,mid,hi);
}
private void merge(Pair[] nums,int lo,int mid,int hi){
//先复制一份
for(int i = lo;i<=hi;i++){
memo[i] = nums[i];
}
int i = lo;
int j = mid+1;
for(int p = lo;p<=hi;p++){
if(i == mid +1){//证明左边全部比当前右边未归位的都要小,不结算
nums[p] = memo[j++];
}else if(j == hi+1){//证明左边此时未归位的比当前右边的全部都大结算,区间是[mid+1,hi],个数就是hi-mid
nums[p] = memo[i++];
count[nums[p].index] += hi - mid;
}else if(memo[i].val <= memo[j].val){//此处结算
nums[p] = memo[i++];
count[nums[p].index] += j-mid-1;
}else{
nums[p] = memo[j++];
}
}
}
}面试题:翻转对
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个***重要翻转对***。
你需要返回给定数组中的重要翻转对的数量。
这道题的变化是,将直接比大小变成了一个等式,我的第一个想法是这样的
for(int p = lo;p<=hi;p++){
if(i == mid+1){
}else if(j == hi+1){
}else if((long)memo[i] < (long)2*memo[j]){
}else{
}
}但是真的可以这样做吗?这样做是会漏解或者多解的。
关键在于边界的情况,也就是当i == mid+1,此时左边数组能够完成nums[i] > 2*nums[j]的数都已经归位了,但是j在向右边推移的过程中,依然有可能存在解,于是这时候解的个数就不确定了,因此这个粗暴的想法要舍弃掉。
那么要怎么做呢?先从暴力的想法入手
for (int i = lo; i <= mid; i++) {
// 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素
for (int j = mid + 1; j <= hi; j++) {
// nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long
if ((long)nums[i] > (long)nums[j] * 2) {
count++;
}
}
}假设我们不断二分,二分出来这些区间,然后完成这些区间内部的计算,最终就可以得到答案,而且这个过程是不需要排序的,因为这个做法无论你排不排序,它每次都会去遍历所有的元素
那么是否可以运用排序后的结果快速计算呢?
可以。首先nums[i] > nums[j]*2的话,而且nums[i+1]>nums[i],那么也就是说从[i,mid]这一段,肯定也是符合条件的,因此当满足nums[i] > nums[j]*2的时候,能够形成的翻转对是mid-i+1个
class Solution {
private int count = 0;
private int[] memo;
public int reversePairs(int[] nums) {
int n = nums.length;
memo = new int[n];
sort(nums,0,n-1);
return count;
}
private void sort(int[] nums,int lo,int hi){
if(lo == hi){return;}
//后序遍历
int mid = lo + ((hi - lo) >> 1);
sort(nums,lo,mid);
sort(nums,mid+1,hi);
merge(nums,lo,mid,hi);
}
//nums[i] > 2*nums[j]
private void merge(int[] nums,int lo,int mid,int hi){
for(int i = lo;i<=hi;i++){
memo[i] = nums[i];
}
int i = lo;
for(int j = mid+1;j<=hi;j++){
while(i <= mid && (long)nums[i] <= (long)2*nums[j]){
i++;
}
count += mid - i +1;
}
//做排序
i = lo;
int j = mid+1;
for(int p = lo;p<=hi;p++){
if(i == mid+1){
nums[p] = memo[j++];
}else if(j == hi+1){
nums[p] = memo[i++];
}else if(memo[i] < memo[j]) {
nums[p] = memo[i++];
}else{
nums[p] = memo[j++];
}
}
}
}面试题:区间和的个数
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
这道题首先从暴力的解法上看,是n方的算法,继续分析
首先这道题并不是直接的叫你求左右两边谁大谁小,而是说是给你一个特殊条件,按照之前那道题的解法的话,那么可以肯定的是在
merge()之前做一波结算操作,然后利用排序的特性降低时间复杂度
在这道题的话,如果我直接对nums进行排序后的结果进行操作,是得不到任何有用的优化的,这是因为每次的下标都在变化,前缀和算了和没算是一样的效果。因此是需要对前缀和进行操作的。
对于区间[lo,hi],我们希望找到[i,j]的和sum[i,j]>=lower && sum[i,j]<=upper
也就是preSum[i,j]>= lower && preSum[i,j]<= upper
自然地,也就是找一个数对,使得这个数对nums[j]-nums[i]在这个区间里面
我们可以固定i,然后寻找j,使得条件成立
class Solution {
private int count = 0;
private long[] memo;
private int lower;
private int upper;
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] preSum = new long[n+1];
memo = new long[n+1];
this.lower = lower;
this.upper = upper;
for(int i = 0;i<n;i++){
preSum[i+1] = preSum[i]+(long)nums[i];
}
sort(preSum,0,n);
return count;
}
//题目是允许有[0,0存在的]
private void sort(long[] nums,int lo,int hi){
if(lo == hi){return;}
//后序遍历
int mid = lo + ((hi - lo) >> 1);
sort(nums,lo,mid);
sort(nums,mid+1,hi);
merge(nums,lo,mid,hi);
}
private void merge(long[] nums,int lo,int mid,int hi){
for(int i = lo;i<=hi;i++){
memo[i] = nums[i];
}
//固定i
int start = mid+1;
int end = mid+1;
for(int i = lo;i<=mid;i++){
//然后检查
while (start<= hi && nums[start]-nums[i]<lower){
start++;
}
end = start;
while (end<= hi && nums[end] - nums[i] <= upper){
end++;
}
count += end - start;
}
//做排序
int i = lo;
int j = mid+1;
for(int p = lo;p<=hi;p++){
if(i == mid+1){
nums[p] = memo[j++];
}else if(j == hi+1){
nums[p] = memo[i++];
}else if(memo[i] < memo[j]) {
nums[p] = memo[i++];
}else{
nums[p] = memo[j++];
}
}
}
}面试题:统计逆序对
题意,就是给你一个数组,如果左边的数是比右边的数要大的,那么这两个数就形成了一个逆序对,给你一个数组,请你求出逆序对的个数
这道题是简单的求取数组左右两边的大小关系
class Solution {
private int count = 0;
private int[] memo;
public int reversePairs(int[] nums) {
int n = nums.length;
memo = new int[n];
sort(nums,0,n-1);
return count;
}
private void sort(int[] nums,int lo,int hi){
if(lo >= hi){return;}
//后序遍历
int mid = lo + ((hi - lo) >> 1);
sort(nums,lo,mid);
sort(nums,mid+1,hi);
merge(nums,lo,mid,hi);
}
private void merge(int[] nums,int lo,int mid,int hi){
for(int i = lo;i<=hi;i++){
memo[i] = nums[i];
}
//做排序
int i = lo;
int j = mid+1;
for(int p = lo;p<=hi;p++){
if(i == mid+1){
nums[p] = memo[j++];
}else if(j == hi+1){
nums[p] = memo[i++];
//[mid+1,hi] = hi - mid -1 +1
count += hi-mid;
}else if(memo[i] <= memo[j]) {
nums[p] = memo[i++];
//[mid+1,j-1] = j-1 - mid -1 +1 = j-mid-1
count += j-mid-1;
}else{//memo[i] > memo[j]
nums[p] = memo[j++];
}
}
}
}从另一个角度看归并排序
所有的递归算法,本质上都是在遍历一棵递归树,然后在节点前中后序位置上执行代码,递归算法本质上就是要告诉每个节点需要做些什么,那么归并排序是要我们干什么?
让左边数组有序(处理左子树)让右边数组有序(处理右子树)合并左右子树(后序操作位置)
那么从解题的套路来讲,有两种,一种是遍历整棵树+外部变量的方法,一种是分解子问题的方法
那么这道题的思路显然是分解子问题的思路,最终在每个节点上执行merge,实现逻辑自洽
时间复杂度
递归算法的时间复杂度 = 子问题的个数*解决一个问题所需要的时间复杂度
执行merge的次数,这一点需要考究,首先我们知道,sort()和merge()是一对操作,sort()将数组划分为两部分,而merge()将两部分的数组合并为一部分
假设待排序的元素有n个,假设二分了x次就会剩下1个元素,那么就是
n/2^x=1,最终解得x=log2n,既然分解要这么多次,那么合并也就要这么多次了
而解决一个问题所需要的时间与每个节点代表的子数组的长度有关,子数组的长度最长是N
综上所述,时间复杂度就是O(NlogN)
private int[] temp;
private void merge(int[] nums,int lo,int mid,int hi){
for(int i = lo;i<=hi;i++){
temp[i] = nums[i];
}
int i = lo;
int j = mid+1;
//双指针法
for(int p = lo; p<=hi; p++){
if(i == mid+1){
nums[p] = temp[j++];
}else if(j == hi+1){
nums[p] = temp[i++];
}else if(temp[i] > temp[j]){
nums[p] = temp[j++];
}else{
nums[p] = temp[i++];
}
}
}
private void sort(int[] nums,int lo,int hi){
if(lo == hi){//当相等的时候就不需要再二分了
return;
}
int mid = lo + ((hi-lo)>>1);
//后序遍历
sort(nums,lo,mid);
sort(nums,mid+1,hi);
merge(nums,lo,mid,hi);
}
public int[] sortArray(int[] nums){
temp = new int[nums.length];
sort(nums,0, nums.length-1);
return nums;
}为什么要一个
temp数组,没有的话可以吗?
这是因为我们无法原地合并,我们在覆盖元素的时候,可能会将之前有序的数组,但是还没有检查的元素覆盖掉,因此需要辅助数组记录原数组。同时提高性能,我们提前new好这个辅助数组,避免在merge过程中进行频繁的new操作
7. 快速排序
void sort(int[] nums,int lo,int hi){
if(lo >= hi){
return;
}
// 对 nums[lo..hi] 进行切分
// 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
int p = partition(nums, lo, hi);
// 去左右子数组进行切分
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}这个一个非常明显的前序遍历的操作,表现为先操作,后遍历
快速排序本质上就是先将一个元素排到它在数组中应该在的位置,然后再对左边/右边的数组中的每个元素都执行这个操作
而这个操作,就对应的是本节点上应该要做的操作,核心操作是:在数组[lo,hi]上挑选一个点p,使得nums[lo,p-1]<=nums[p] && nums[p+1,hi]>=nums[p],因此可以看出partition()函数本质上就是将这个元素排好序,它需要左右两边数组有序吗?不需要,因此采用前序遍历即可
那么在排序的过程中,我们根据根左右的遍历方向,我们知道左边的节点肯定是小的,右边的节点肯定是大的,因此在计算机递归过程中,如果我们刻意去记录根节点的连接情况,就会产生一棵二叉搜索树
快速排序过程就是在构造一棵二叉搜索树
那么最常见的问题,当它没有做一种平衡化的操作的时候,就会导致其退化为链表,其根本原因是其根节点的选取不恰当,比如说你选取的根节点是数组中的最大值/最小值,都将会导致其退化为链表
时间复杂度的讨论留到后面(重点、难点)
为了避免这种极端的情况,需要引入随机性,常见的方式就是对数组进行洗牌算法,或者随机选取分界点,尽量避免这样的情况发生
public class Quick {
public static void sort(int[] nums){
shuffle(nums);
sort(nums,0,nums.length-1);
}
public static void sort(int[] nums,int lo,int hi){
if(lo >= hi){
return;
}
//前序
int p = partition(nums,lo,hi);
sort(nums,lo,p-1);
sort(nums,p+1,hi);
}
//对[lo,hi]进行划分
private static int partition(int[] nums,int lo,int hi){
int pivot = nums[lo];
int i = lo+1;
int j = hi;
//使得[lo,i)<=pivot,(j,hi]>pivot
//我们定义区间[lo,i)都是小于等于pivot的
//定义区间(j,hi]都是大于pivot
//因此在初始情况下区间都是空的,如果要符合定义,那么就是要开区间
//我们需要确保[lo,i)∪(j,hi] = [lo,hi]
//当i < j的时候,是普遍情况,很多元素没有检查
//当i == j的时候,这时候就漏掉了一个元素没有检查
//当i > j的时候,这时候可以完全覆盖区间,所有元素均已检查
while(i <= j){
while (i<hi && nums[i] <= pivot){
i++;
}
//当跳出来的时候,有两种情况 i == hi || nums[i] > pivot
//什么时候会i == hi?从i = lo+1到hi
//区间[lo+1,hi]内的值全部都比pivot要小,这时候i走到了hi
while (j>lo && nums[j]>pivot){
j--;
}
//有两种情况,j == lo || nums[j] <= pivot
//j == lo,从[hi,lo+1],这个区间里面的值全部都比pivot要大
if(i>j){
//什么时候会触发这个条件?
//首先你需要知道的是当i == hi的时候,这时候由于[lo+1,hi]的值全部都比pivot要小
//那么j会等于多少呢?j会等于hi,i=hi,h=hi,i=j,此时区间合法,不需要交换
//当j==lo的时候,这时候由于[lo+1,hi]中的所有元素都比pivot要大
//i会等于lo+1,这时候就产生了i>j,此时区间合法,不需要交换,将pivot交换即可
//而当i!=hi&&j!=lo的时候,这时候分为两种情况
//i检测到第一个nums[i] > pivot的时候,break掉
//j检测到第一个nums[j] <= pivot的时候,break掉
//这时候,如果i>j,就说明i走到了pivot的右边,而j走到了pivot的左边了
//显然,nums[j]<=pivot,这时候直接交换即可,因为找到了边界
//如果i<j,就证明i和j就都在各自的边界内部,那么我们就要交换他们的位置,维护一个合法区间
break;
}
swap(nums,i,j);
}
//此时i>j
swap(nums,lo,j);
return j;
}
//洗牌算法
private static void shuffle(int[] nums){
Random rand = new Random();
int n = nums.length;
for(int i = 0;i<n;i++){
//生成从`[i,n-1]`之间的随机数
int r = i + rand.nextInt(n-i);
swap(nums,i,r);
}
}
private static void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = nums[i];
}
}
既然是递归,那么就可以用公式:子问题的数量*处理每个子问题所需要的时间
首先处理每个子问题的过程是一个循环,这个循环最差情况下将会导致每个子问题处理N个元素
然后是子问题的数量,子问题的数量可以沿用我们之前检测归并排序的过程
快速排序本质上也是将N个元素划分为两半,但是归并排序是每次都取mid,从而导致它能够获得稳定划分次数
但是快速排序的划分是根据元素的大小,有以下情况
- 最差情况下,将会导致一边的节点为空,退化为链表,也就是说一层只有一个节点,N个问题
- 最好情况下,将会导致选取的
pivot都恰好在中间,这时候就会成为二叉树,而二叉树的话就是log2N个问题
假设需要划分x次,每次都是二分,那么也就是N/2^x = 1,解得x = log2N
最好情况下,快速排序的时间复杂度为o(NlogN),空间复杂度为O(logN)
最坏情况下,快速排序的时间复杂度为O(N^2),空间复杂度为O(N)
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
public int findKthLargest(int[] nums, int k) {
shuffle(nums);
int lo = 0,hi = nums.length-1;
k = nums.length - k;
while (lo <= hi){
int p = partition(nums,lo,hi);
if(p < k){
lo = p+1;
}else if(p > k ){
hi = hi-1;
}else{
return nums[p];
}
}
return -1;
}
/**
* 打乱数组的顺序,避免极端情况
* @param nums
*/
private void shuffle(int[] nums){
Random random = new Random();
int n = nums.length;
for(int i = 0;i<n;i++){
//n-i
int r = i + random.nextInt(n-i);
swap(nums,i,r);
}
}
/**
* 在[lo,hi]中产生一个分界点
* @param nums
* @param lo
* @param hi
* @return
*/
private int partition(int[] nums,int lo,int hi){
//将lo作为哨兵,将哨兵放到合法的位置上
int pivot = nums[lo];
//将[lo+1,hi]进行位置的交换
int i = lo+1,j = hi;
while(i <= j){
while(i<=hi && nums[i] < pivot){
i++;
}
while (j> lo && nums[j] >= pivot){
j--;
}
if(i>=j){
break;
}
swap(nums,i,j);
}
swap(nums,lo,j);
return j;
}
private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
