宿州城市建设投资网站,做网站的素材和步骤,软件app大全免费,张掖网站设计公司#x1f3a5; 个人主页#xff1a;Dikz12#x1f525;个人专栏#xff1a;算法(Java)#x1f4d5;格言#xff1a;吾愚多不敏#xff0c;而愿加学欢迎大家#x1f44d;点赞✍评论⭐收藏
目录
颜色分类
题目描述
题解
代码实现
排序数组
题目描述 题解
代码… 个人主页Dikz12个人专栏算法(Java)格言吾愚多不敏而愿加学欢迎大家点赞✍评论⭐收藏
目录
颜色分类
题目描述
题解
代码实现
排序数组
题目描述 题解
代码实现
数组中的第k个最大元素
题目描述 题解
编辑 代码实现
库存管理III( 最小k个数)
题目描述
编辑 题解
代码实现 分治分而治之. 颜色分类
题目描述 题解 解法三指针数组分三块. 代码实现 public void sortColors(int[] nums) {int i 0, left -1, right nums.length;while(i right) {if (nums[i] 0) {swap(nums,left,i);} else if (nums[i] 1) {i;}else {swap(nums,--right,i);}} }public void swap(int[] nums, int i , int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;}
排序数组
题目描述 题解 解法快速排序数组分三块随机选择基准. 快排最核⼼的⼀步就是 Partition (分割数 据)将数据按照⼀个标准分成左右两部分。 这里 不是使用的是将数组分成两部分挖坑法、Hoare法。 而是使⽤荷兰国旗问题的思想将数组划分为 左 中 右 三部分左边是⽐基准元素⼩的数据 中间是与基准元素相同的数据右边是⽐基准元素⼤的数据。然后再去递归的排序左边部分和右边 部分即可可以舍去⼤量的中间部分。 在处理数据量有很多重复的情况下效率会⼤⼤提升 数组分三块过程就跟上题一样就不在进行详述.
优化方式有随机选择基准 和 三位取中. 代码实现 public int[] sortArray(int[] nums) {qsort(nums,0,nums.length - 1);return nums;}public void qsort(int[] nums,int l , int r) {//递归结束if (l r) {return;}//数组分三块int key nums[new Random().nextInt(r - l 1) l];int left l - 1, i l, right r 1;while(i right) {if(nums[i] key) {swap(nums,left,i);}else if (nums[i] key) {i;} else {swap(nums,--right,i);}}//[0,left] [left1,right-1] [right,r]qsort(nums,l,left);qsort(nums,right,r);}public void swap(int[] nums,int i, int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;} 挖坑法、Hoare法优化 数组分三块优化 数组中的第k个最大元素
题目描述 题解
解法快速选择算法数组分三块随机选取基准元素 。 在快排中当我们把数组「分成三块」之后 [l, left] [left 1, right - 1] [right, r] 我们可以通过计算每⼀个区间内元素的「个数」进⽽推断出我们要找的元素是 在「哪⼀个区间」⾥⾯。 那么我们可以直接去「相应的区间」去寻找最终结果就好了。 代码实现 public int findKthLargest(int[] nums, int k) {return qsort(nums,0,nums.length-1,k);}public int qsort(int[] nums,int l ,int r, int k) {//结束条件if (l r) {return nums[l];}//1.随机选取基准int key nums[new Random().nextInt(r - l 1) l];//2.数组分三块int i l , left l - 1, right r 1;while(i right) {if(nums[i] key) {swap(nums,left,i);} else if (nums[i] key) {i;} else{swap(nums,--right,i);}}// 3.区间个数 [l,left] [left 1, right - 1] [right,r]int b right - left - 1, c r - right 1;if(c k) {return qsort(nums,right,r,k);} else if (b c k) {return key;} else {return qsort(nums,l,left,k - c - b);}}public void swap(int[] nums, int i , int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;}
库存管理III( 最小k个数)
题目描述 题解
解法一堆排.大根堆O(NlogN).
解法二快速选择算法数组分三块随机选取基准元素 O(N) 在快排中当我们把数组「分成三块」之后 [l, left] [left 1, right - 1] [right, r] 我们可以通过计算每⼀个区间内元素的「个数」进⽽推断出最⼩的 k 个数在哪 些区间⾥⾯。 那么我们可以直接去「相应的区间」继续划分数组即可。 代码实现 public int[] inventoryManagement(int[] nums, int cnt) {qsort(nums,0,nums.length-1,cnt);int[] ret new int[cnt];for(int i 0; i cnt; i) {ret[i] nums[i];}return ret;}public void qsort(int[] nums, int l, int r, int k) {if(l r) {return;}//1.随机选取基准int key nums[new Random().nextInt(r - l 1) l];//2.数组分三块int i l, left l - 1,right r 1;while(i right) {if(nums[i] key) {swap(nums,left,i);} else if (nums[i] key) {i;} else {swap(nums,--right,i);}}//3. [l,left] [left1,right-1] [right,r]int a left - l 1, b right - left - 1;if (a k) {qsort(nums,l,left,k);} else if(a b k) {return;} else {qsort(nums,right,r,k - a - b);}}public void swap(int[] nums, int i , int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;}
