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

做网站要多少钱 知乎百度seo优化推广公司

做网站要多少钱 知乎,百度seo优化推广公司,买网站不给我备案,两学一做夜校网站题目链接:力扣 解题思路: 方法一:基于快速排序 因为题目中只需要找到第k大的元素,而快速排序中,每一趟排序都可以确定一个最终元素的位置。 当使用快速排序对数组进行降序排序时,那么如果有一趟排序过程…

题目链接:力扣

解题思路:

方法一:基于快速排序

因为题目中只需要找到第k大的元素,而快速排序中,每一趟排序都可以确定一个最终元素的位置。

当使用快速排序对数组进行降序排序时,那么如果有一趟排序过程中,确定元素的最终位置为k-1(索引从0开始),那么,该元素就是第k大的元素

具体思想下:

  1. 利用快排,对数组num[left,...,right]进行降序排序,在一趟排序过程中,可以确定一个元素的最终位置p,将数组划分为三部分,num[left,...,p-1],nums[p],nums[p+1,right],并且满足
    1. num[left,...,p-1] >= nums[p]
    2. num[p+1,right] <=nums[p]
    3. 即p位置以前的元素是数组中比p位置元素大的元素(此时p位置以前的元素不一定有序,但是肯定都大于等于p位置的元素),而num[p]是第p+1大的元素
  2. 因为需要找到的是第k大的元素:
    1. 如果k < p,那么第k大的元素肯定在num[left,...,p-1]内,这个时候只需要对右半部分区间进行快排
    2. 如果k > p,那么第k大的元素肯定在nums[p+1,right]区间内,这个时候只需要对左半部分区间进行快排
    3. 如果 p= k-1,那么nums[p]就是第k大的元素
  3. 注意这种方式并不要求最终数组中的元素有序,每次只会对左半部分或者右半部分进行快排,减少了一半的快排调用

AC代码:

class Solution {public static int findKthLargest(int[] nums, int k) {return quickSortFindK(nums, 0, nums.length - 1, k);}public static int quickSortFindK(int[] nums, int left, int right, int k) {//选取枢轴元素int pivot = nums[left];int low = left;int high = right;while (low < high) {while (low < high && nums[high] <= pivot)high--;nums[low] = nums[high];while (low < high && nums[low] >= pivot)low++;nums[high] = nums[low];}//low(或者right)就是这趟排序中枢轴元素的最终位置nums[low] = pivot;if (low == k - 1) {return pivot;} else if (low > k - 1) {return quickSortFindK(nums, left, low - 1, k);} else {return quickSortFindK(nums, low + 1, right, k);}}
}

 

快速排序的最好时间复杂度是O(nlogn),最坏时间复杂度为O(n^2),平均时间复杂度为O(nlogn)

快速排序在元素有序的情况下效率是最低。

不过可以通过在某些情况下,快速排序可以达到期望为线性的时间复杂度,即O(n),也就是在每次排序前随机的交换两个元素(个人理解可能是为了让元素变乱,不那么有序,越乱越快,算法导论中在9.2 期望为线性的选择算法进行了证明,还没有学习,先在此记录下),它的时间代价的期望是 O(n)

具体代码实现,就是在排序前,加上下面的代码

//随机生成一个位置,该位置的范围为[left,right]
//然后将该位置的元素与最后一个元素进行交换,让数组变得不那么有序,
//放置出现有序的情况下快排的时间复杂度退化为o(n^2)
int randomIndex = random.nextInt(right - left + 1) + left;
int tem = nums[randomIndex];
nums[randomIndex] = nums[right];
nums[right] = tem;

AC代码:

class Solution {static Random random = new Random();public static int findKthLargest(int[] nums, int k) {return quickSortFindK(nums, 0, nums.length - 1, k);}public static int quickSortFindK(int[] nums, int left, int right, int k) {int randomIndex = random.nextInt(right - left + 1) + left;int tem = nums[randomIndex];nums[randomIndex] = nums[right];nums[right] = tem;int pivot = nums[left];int low = left;int high = right;while (low < high) {while (low < high && nums[high] <= pivot)high--;nums[low] = nums[high];while (low < high && nums[low] >= pivot)low++;nums[high] = nums[low];}nums[low] = pivot;if (low == k - 1) {return pivot;} else if (low > k - 1) {return quickSortFindK(nums, left, low - 1, k);} else {return quickSortFindK(nums, low + 1, right, k);}}
}

时间上确实有了一些提升

解法二:堆排序。

建立小根堆,最后让小根堆里的元素个数保持在k个,那么此时栈顶的元素就是k个元素中最小的,即第k大的元素

可以通过优先级队列来模拟小根堆

AC代码

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>();for (int num : nums) {//已经有k个元素了,当前元素比堆顶元素还小,不可能是第k大的元素,跳过if (queue.size()==k&&queue.peek()>=num){continue;}queue.offer(num);}while (queue.size()>k){queue.poll();}return queue.peek();}
}

解法三:大根堆

  1. 对于区间[0,n]建立大根堆后,此时堆顶元素nums[0]为最大值,可以将堆顶元素与最后一个元素交换,即将最大值移动到数组最后,
  2. 然后将[0,n-1]区间调整为大根堆,此时堆顶nums[0]就是第二大的值,将堆顶元素与倒数第二个元素交换,即倒数第二大的值移动到数组倒数第二个位置
  3. 然后将[0,n-2]区间调整为大根堆...
  4. 调整 k-1此后的大根堆,此时的堆顶元素就是第k大的元素

大根堆可以使用优先级队列实现,传递一个降序的比较器。

这里复习下堆排序,手动写了一个大根堆

AC代码:

class Solution {public static int findKthLargest(int[] nums, int k) {createHeap(nums);for (int i = nums.length - 1; i > nums.length - k; i--) {int tem = nums[0];nums[0] = nums[i];nums[i] = tem;heapAdjust(nums, 0, i - 1);}return nums[0];}//建初堆public static void createHeap(int[] nums) {for (int i = nums.length / 2 - 1; i >= 0; i--) {heapAdjust(nums, i, nums.length-1);}}/*调整成大根堆nums[begin+1,end]已经是大根堆,将nums[begin,end]调整为以nums[begin]为根的大根堆*/public static void heapAdjust(int[] nums, int begin, int end) {int tem = nums[begin];for (int i = 2 * begin + 1; i <= end; i = i * 2 + 1) {if (i+1 <= end && nums[i] < nums[i+1])//j为左右子树中较大的子树的下标i++;//tem大于左右子树,已经是大根堆,退出if (tem >= nums[i])break;nums[begin] = nums[i];//更新待插入的位置begin = i;}//tem应该存放的位置nums[begin] = tem;}
}

http://www.zhongyajixie.com/news/47610.html

相关文章:

  • 小程序排名帝搜软件sem880官网广州营销seo
  • 网站一般做多大像素建站公司排名
  • 中山网站建设工作室网站怎么制作教程
  • 国外什么网站是做外贸西安网站建设制作
  • 广州南沙区建设和交通局网站指数分布的期望和方差
  • 石家庄网站建设策划方案写一篇推广商品的软文
  • 西安网站建设管理百度店铺注册
  • 垂直门户网站怎么做深圳seo关键词优化外包公司
  • 怎么做产品网站北京百度推广代运营
  • 校园文化建设网站百度大搜推广
  • 免费商城网站模板seo优化排名推广
  • 网站建设中单页面抖音seo源码搭建
  • wordpress胖鼠采集培训seo
  • 广州网匠营销型网站建设公司南宁网站seo优化公司
  • 企业vi设计公司哪家好厦门seo百度快照优化
  • 建设网站什么软件比较好品牌运营公司
  • 万江做网站的公司汕头seo不错
  • 政府门户网站建设要求适合发表个人文章的平台
  • 在线做ppt的网站常宁seo外包
  • 网站seo谷歌百度网站首页网址
  • 做网站那家好做外贸有哪些网站平台
  • 网站案例武汉关键词seo
  • 快速做效果图的网站叫什么区别南京seo代理
  • 做网站上凡科广告发布平台app
  • 上海网站公安局备案企业网站建设推广
  • 做网站时如何确定网站主题友情链接
  • 做美图+网站有哪些东西以图搜图
  • 申请网站建设拼多多代运营一般多少钱
  • 六安做网站公司佛山网站优化软件
  • dede网站seoseo关键词分类