循环阵列宽度搜索格式
循环阵列宽度搜索格式
提问于 2015-07-10 07:00:09
问题的题目可能有点不正确，但我不知道如何描述我的问题。
我希望对数组的键进行重构，这样循环将用以下模式跳转：
示例1：
keys from 1,2,3,4,5,6,7,8,9 will lead to 1,9,5,3,7,2,6,4,8- 取第一个元素-1
- 最后一个元素-9
- 取中间(1+9)/2 =5
- 到上半场，在1和5-3的中间。
- 跳到下半场，在5和9-7的中间。
- 回到上半场的前半部分，拿2
- 回到下半场的上半段，拿6。
- 回到上半场的下半段，拿4。
- 回到下半场的下半段，拿8。
当然，这是一个理想化的例子，所有的东西都可以很好地分割。如果不是这样的话，那么你就必须用地板和细胞来划分新的元素。
示例2：
key from 1,2,3,4,5,6,7,8,9,10 will lead to 1,10,5,6,3,8,2,7,4,9由于我对算法和数据结构知之甚少，我试着使用递归/分而治之的方法，但我没能实现半个半个之间的跳转。
因此，我认为我必须增加参数，如分割的一半的长度和位置，但在这里，我失去了实现。
对我来说，有趣的问题是:我的思维是否复杂，有没有一个更容易解决的办法？还是这个问题真的这么复杂？
我很高兴任何关于文学或代码片段的建议来尝试它。
谢谢，并向斯蒂文问好
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-07-10 15:34:10
我不确定你是否能通过递归或分治来实现这个算法。但是你可以用广度优先搜索来做这件事。下面是python伪代码，其中有一个队列，其元素是间隔。
#initialize queue Q with the whole interval
n = len(your_list)
# breadth first search
Q.push([0, n-1])
while Q not empty:
itv = q.pop_front()
process(itv) # print the middle element of interval itv, etc.
itv_1, itv_2 = divide_interval_into_halves(itv)
if len(itv_1) > 0:
Q.push(itv_1)
if len(itv_1) > 0:
Q.push(itv_2)希望它有帮助:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31334439
复制相关文章
相似问题
腾讯云开发者
