这道关于《数据结构》的题该如何做呢?
1个回答
展开全部
如果与后继元素位置交换了岂不是就不再递增有序了?...那么就没有什么性质了?
不过看题目意思好像是只要求进行一次操作,而且只要求查找到它的时间最短。
有一种比较简单的做法,就是二分法。
每次二分这个有序数组中的一个位置mid=(l+r)/2。然后判断这个元素和x的大小关系。
如果a[mid]>x,那么可以将r移动到mid,如果a[mid]>=x,那么可以将l移动到mid。一直到区间大小为1,就是那个元素。
其中l的初始值为1.r的初始值为n。
上面只是查找方法,但是数组中的添加很慢。
所以可以使用一种神奇的数据结构叫平衡树或者二叉搜索树。[但是一看就不是要问这个]。
不过看题目意思好像是只要求进行一次操作,而且只要求查找到它的时间最短。
有一种比较简单的做法,就是二分法。
每次二分这个有序数组中的一个位置mid=(l+r)/2。然后判断这个元素和x的大小关系。
如果a[mid]>x,那么可以将r移动到mid,如果a[mid]>=x,那么可以将l移动到mid。一直到区间大小为1,就是那个元素。
其中l的初始值为1.r的初始值为n。
上面只是查找方法,但是数组中的添加很慢。
所以可以使用一种神奇的数据结构叫平衡树或者二叉搜索树。[但是一看就不是要问这个]。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询