当前位置: 首页 > news >正文

做推送实用网站百度助手应用商店下载安装

做推送实用网站,百度助手应用商店下载安装,工信部网站域名备案,业务员自己做网站力扣75.颜色分类 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sor…

力扣75.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

 

class Solution { //时间复杂度为O(n)//其实,变量 zero 相当于我们在三路快速排序算法中的 lt;//变量 two 相当于我们在三路快速排序算法中的 gt。public void sortColors(int[] nums) {// nums[0...zero] == 0, nums[zero + 1, i] == 1, nums[two, n - 1] == 2// 定义三个指针:zero、i、two,分别表示0的最右边界、当前处理的元素、2的最左边界int zero = -1, i = 0, two = nums.length;while(i < two){// 当前处理元素的指针小于2的最左边界时,继续循环// 如果当前元素为0,将其与zero右边的元素交换,并将zero和i都向右移动一位if(nums[i] == 0){zero++;swap(nums,zero,i);i++;}// 如果当前元素为2,将其与two左边的元素交换,并将two向左移动一位else if (nums[i] == 2){ // 注意此时不需要i右移,因为交换后的元素还需要继续判断two --;swap(nums, i, two);}else{ //如果当前元素是1,不需要操作,直接继续向右遍历i ++;}}}// 交换数组中指定位置的两个元素private void swap(int[] nums, int i, int j){int t = nums[i];nums[i]= nums[j];nums[j] = t;}
}


我们首先来封装一个 selectK 的方法。封装好了这个方法以后,这三个问题都可
以快速求解。
我们的 selectK 的接口是这样的:
// 在 arr[l...r] 的范围里求解整个数组的第 k 小元素并返回
// k 是索引,即从 0 开始计算
int selectK(int[] arr, int l, int r, int k, Random rnd)
因为我们的 partition 过程需要随机选取标定点,所以我们还需要传一个 Random(快排的优化)
类的对象 rnd。
定义好函数签名以后,下面我们来书写相应的逻辑。
首先,selectK 的过程,我们就是要执行一遍 partition。在这里,我使用双路快速
排序的 partition。
注意,因为在这个问题中,我们肯定我们处理的数据类型是 int,所以,在代码
中,我不再使用泛型:

private int partition(int[] arr, int l, int r, Random rnd){// 生成 [l, r] 之间的随机索引int p = l + rnd.nextInt(r - l + 1);swap(arr, l, p);// arr[l+1...i-1] <= v; arr[j+1...r] >= vint i = l + 1, j = r;while(true){while(i <= j && arr[i] < arr[l])i ++;while(j >= i && arr[j] > arr[l])j --;if(i >= j) break;swap(arr, i, j);i ++;j --;
}swap(arr, l, j);return j;
}
private void swap(int[] arr, int i, int j){int t = arr[i];arr[i] = arr[j];arr[j] = t;
}

有了 partition,我们的 selectK 的主题逻辑非常简单。

首先,进行 partition,假设结果是 p。我们只需要将 k 和 p 做比较。

  • 如果 k == p,直接返回 arr[p] 即可;
  • 如果 k < p,在 arr[l, p - 1] 的范围继续找,即调用 selectK(arr, l, p - 1, k, rnd);
  • 如果 k > p,在 arr[p + 1, r] 的范围继续找,即调用 selectK(arr, p + 1, r, k, rnd);

就有了下面的代码:

private int selectK(int[] arr, int l, int r, int k, Random rnd){
int p = partition(arr, l, r, rnd);
if(k == p) return arr[p];
if(k < p) return selectK(arr, l, p - 1, k, rnd);return selectK(arr, p + 1, r, k, rnd);
}

这样,我们就完成了 select K 的过程。是不是非常简单!

下面,我们用我们写的 select K,先来解决 Leetcode 上第 215 号问题:

这个问题是求第 k 大元素,但是我们的 selectK 求得是第 k 小元素。怎么办?
非常简单,我们只需要在调用 select K 之前,将求第 k 大元素的这个 k,转换成
对应求的是第几小元素对应的索引就好了。
按照题目描述,如果 k 是 1,对应就是要找最大元素,那么相应的我们的
select K 的索引,就是 nums.length - 1。(如果10个数,K=1,第一个最大的数,就是SelectK索引为9的那个的元素)
如果 k 是 nums.length,其实就是求最小元素,那么相应的我们的 selectK 的
索引,就是 0。  (如果10个数,第10个最大的数,就是SelectK索引为0的那个的元素,最小值)
他们之间的转换关系是 nums.length - k。

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

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

import java.util.Random; //导入Random包
class Solution {public int findKthLargest(int[] nums, int k) {//只有两行,其他的内容全部复用我们上面实现的 selectK,是不是很酷?//我们的SelectK是第K最小元素,所以这里findKthLargest传入下标要处理一下//转换关系是 nums.length - kRandom rnd = new Random();return selectK(nums, 0, nums.length - 1, nums.length - k, rnd);}//有了 partition,我们的 selectK 的主题逻辑非常简单。private int selectK(int[] arr, int l, int r, int k, Random rnd){//首先,进行 partition,假设返回值结果是 p。我们只需要将 k 和 p 做比较。int p = partition(arr, l, r, rnd); //如果 k == p,直接返回 arr[p] 即可;if(k == p) return arr[p]; //如果 k < p,在 arr[l, p - 1] 的范围继续找,即调用 selectK(arr, l, p - 1, k, rnd);if(k < p) return selectK(arr, l, p - 1, k, rnd); //如果 k > p,在 arr[p + 1, r] 的范围继续找,即调用 selectK(arr, p + 1, r, k, rnd);return selectK(arr, p + 1, r, k, rnd);
}private int partition(int[] arr, int l, int r, Random rnd){// 生成 [l, r] 之间的随机索引int p = l + rnd.nextInt(r - l + 1);swap(arr, l, p);// arr[l+1...i-1] <= v; arr[j+1...r] >= vint i = l + 1, j = r;while(true){while(i <= j && arr[i] < arr[l])i ++;while(j >= i && arr[j] > arr[l])j --;if(i >= j) break;swap(arr, i, j);i ++;j --;}swap(arr, l, j);return j;}//数组指定索引,两数交换private void swap(int[] arr, int i, int j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}
}

http://www.qdjiajiao.com/news/842.html

相关文章:

  • 茂南网站开发公司抖音seo公司
  • 扬州将建设网站营销网站建设教学
  • 网站如何在百度上做推广方案网站运营与维护
  • onethink做的企业网站实体店营销方案
  • 向国旗敬礼 做新时代好少年网站整站营销系统
  • 哪个网站做童装批发免费b站推广网站入口2020
  • 视频网站是怎么做权限管理的广州seo怎么做
  • 抖音代运营商家谈判话术西安网络优化大的公司
  • 网站底部留言代码色盲测试图片
  • 网站 优化手机版淘宝怎么优化关键词步骤
  • 石家庄做网站公司的电话网站发布与推广怎么写
  • 余姚网站建设 熊掌号百度优化怎么做
  • 深圳百度网站排名优化培训网站设计
  • 武汉网站建设老牌公司windows优化大师破解版
  • 国家电网网站制作网站seo诊断报告
  • vs2008做html5网站软件网站关键词优化
  • 有域名没有服务器怎么做网站谷歌广告上海有限公司官网
  • wordpress用那个采集器宁波最好的seo外包
  • 做网站后端要什么技术个人网站推广方法
  • 企业网站建百度官网app下载安装
  • 网站客服代码关键词网络推广企业
  • 中医网站源码手机最新产品新闻
  • 凡科做网站好吗合肥做网站的公司有哪些
  • 易瑞通网站建设实体店引流推广方法
  • 哪里做网站最好百度seo快速排名优化
  • 益阳哪里做网站企业整站优化
  • 用asp.net做的网站营销咨询服务
  • 网站建设网络门户seo接单平台
  • 枣庄网站建设哪家好sem竞价培训班
  • 长沙找工作哪个网站好福州网站建设团队