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

镇江网站设计建设营销网店推广的软文

镇江网站设计建设,营销网店推广的软文,手机网站如何建站,dw做不了动态网站asp题目:https://www.acwing.com/problem/content/description/787/对应视频讲解:https://www.acwing.com/video/227/题目描述注意本题数据已加强。快速排序过程中,如果每次取区间起点或者终点作为分界点,则会超时。分界点换成随机值…
题目:https://www.acwing.com/problem/content/description/787/
对应视频讲解:https://www.acwing.com/video/227/

题目描述

注意本题数据已加强。

快速排序过程中,如果每次取区间起点或者终点作为分界点,则会超时。

分界点换成随机值,或者区间中点即可。


解题思路及代码

(一)解题思路及举例

分治策略:将规模为n的原问题分解为规模减半的子问题,分别求解每个子问题,然后把子问题的解进行综合,从而得到原问题的解

举例如下:

给定一个数组,如 [3, 1, 2, 3, 5]

给定两个指针,分别指向数组的最左侧和最右侧的外侧,再将两指针分别往中间移动一位,此时指针i指向3,指针j指向5,即:

  [3, 1, 2, 3, 5]i                j[3, 1, 2, 3, 5]i            j

假设把最左侧的数作为枢轴值/基准值,即x=3【但由于本题数据已增强,在代码里,只能取区间中点或随机值作为分界点,若取区间起点/终点,会超时

枢轴值/基准值:用来将整个序列分为两个部分,再分别进行快速排序

确定枢轴值后,从左往右移动i,若i指向的数小于x,则一直移动,直到遇到≥x的数停止。很显然,上来的3就>=x,i停在3的位置

同理,从右往左移动j,若j指向的数大于x,则一直移动,直到遇到≤x的数停止。很显然,5>2,j左移;移到3时停止。如下:

[3, 1, 2, 3, 5]i         j

交换i和j指向的两个数,数组变为 [3, 1, 2, 3, 5],由于交换的是3和3,数组不变。两个指针分别往中间移动一位,如下:

[3, 1, 2, 3, 5]i   j

i指向1<3,右移,2<3,右移,遇到3时停止;j指向2,不满足>3,停止在2的位置,如下:

[3, 1, 2, 3, 5]j  i   

由于此时两指针已经彼此穿过,故不能交换两个数

再以j指向位置作为分界,对其左右两部分分别进行快速排序:

首先看左侧:[3, 1, 2] 都≤3

  • 枢轴值为区间起点3,指针i指向3,指针j指向2

  • i指向3不是<3的,故i停在该位置

  • j指向2不是>3的,故j停在该位置

  • 交换两数,数组变为 [2, 1, 3],同时两指针均往中间移动一位,都指向1

  • i指向1满足<3,右移一位,指向3;j指向1不满足>3,停止。如下:

[2, 1, 3]j  i   

同理,此时两指针已经彼此穿过,不能交换两个数。再以j为分界,划分为 [2, 1] 和 [3]

  • 对于 [2, 1],枢轴值为区间起点2,i指向2并停止,j指向1并停止,交换两数,变为 [1, 2]。两指针均往中间移动一位,彼此穿过,跳出循环,返回 [1, 2]

  • [3] 只有一个数,不需要排序,直接返回

综上,左半部分最终返回 [1, 2, 3]

再看右侧:[3, 5] 都≥3

  • 枢轴值为区间起点3,指针i指向3,指针j指向5

  • i指向3不满足<3,停止;j指向5,满足>3,左移一位到3,不满足>3,停止

  • 此时两指针都指向3,位于一个位置,跳出循环,返回 [3, 5]

综上,右半部分最终返回 [3, 5]

合并左右两部分结果即得到排好序的序列输出:[1, 2, 3, 3, 5]


(二)代码

n = int(input())
nums = list(map(int, input().split()))   # 通过map实现类型转换,返回listdef QuickSort(arr, left, right):if left >= right:return arr# 1、确定分界点i, j, x = left-1, right+1, arr[(left+right) // 2]   # 左指针 右指针 分界点(中间值,向下取整)while i < j :i+=1j-=1# 左边区间的值放小于x,指针不断右移;右边的相反while arr[i] < x :i += 1while arr[j] > x :j -= 1# 2、调整区间,使得左边区间是<=x的数,右边区间是>=x的数# 移动过后,如果i还是小于j,说明左边或者右边有逆向数据,所以交换if i < j:arr[i], arr[j] = arr[j], arr[i]# 3、递归处理左右两个区间   QuickSort(arr, left, j)QuickSort(arr, j+1, right)QuickSort(nums, 0, n-1)
print(' '.join(map(str, nums)))

知识点总结

(一)map()函数

根据提供的函数对指定的序列做映射,返回一个集合

map(function, iterable)

参数:

  • function:接受一个函数名

  • iterable:接受一个或多个可迭代的序列

把函数依次作用在list中的每一个元素上,得到一个新的list并返回(map不改变原list,而是返回一个新list)

(二).join()函数

是一个字符串操作函数

str.join(item)

参数:

  • str:字符串/字符

  • item:一个成员,注意括号里只能有一个成员

例子:

','.join('abc')
# 将字符串abc中的每个成员以字符,分隔开  再拼接成一个字符串
http://www.khdw.cn/news/25410.html

相关文章:

  • 做红包网站是犯法的吗厦门seo服务
  • 百度建设网站seo是哪个英文的缩写
  • 做网站赣州网店推广的重要性
  • 网站模板免费吗品牌营销策略分析
  • 网站上传图片大小限制百度竞价推广方案
  • 阿里巴巴网站是怎么做的91永久海外地域网名
  • 做网站做什么赚钱广告外链平台
  • 建站快车优势百度信息流广告推广
  • 阿里云ecs网站建设网站搜索优化找哪家
  • 人工智能营销网站开发免费学生网页制作成品
  • 金华公司建站模板经典营销案例分析
  • 网站建设登录注册怎么做seo标签怎么优化
  • 建设网站的市场背景黑帽seo寄生虫
  • 网站建设维护协议书软文写作的技巧
  • 武汉网站建设与制作服务百度指数预测
  • 专题网站建设方案网站可以自己建立吗
  • 哪个网站做图书广告好国内最新十大新闻
  • 江西智能网站建设活动推广朋友圈文案
  • 网站后台上传案例能同步到博客吗高端网站定制
  • 中期通网站建设免费创建网站软件
  • 网站备案 接入商名称发布新闻最快的网站
  • 比较好的外贸公司seo常用工具有哪些
  • 杭州制造业企业做网站青岛关键词排名哪家好
  • 汕头网站优化哪家好西安seo网络优化公司
  • 郑州企业网站优化公司网站cms
  • 党建网站 自身建设重庆seo顾问
  • 有没有网站建设的兼职如何注册百度账号
  • 电子商务网站的建设心得体会china东莞seo
  • 长春仿站定制模板建站营销软文网站
  • 织梦做网站也是模板吗常见的网络营销方式有哪几种