这道关于《数据结构》的题该如何做呢?

 我来答
袁世平1
2016-03-15 · TA获得超过536个赞
知道小有建树答主
回答量:459
采纳率:0%
帮助的人:392万
展开全部
如果与后继元素位置交换了岂不是就不再递增有序了?...那么就没有什么性质了?

不过看题目意思好像是只要求进行一次操作,而且只要求查找到它的时间最短。

有一种比较简单的做法,就是二分法。
每次二分这个有序数组中的一个位置mid=(l+r)/2。然后判断这个元素和x的大小关系。
如果a[mid]>x,那么可以将r移动到mid,如果a[mid]>=x,那么可以将l移动到mid。一直到区间大小为1,就是那个元素。
其中l的初始值为1.r的初始值为n。

上面只是查找方法,但是数组中的添加很慢。
所以可以使用一种神奇的数据结构叫平衡树或者二叉搜索树。[但是一看就不是要问这个]。
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式