时间戳

首页 > 解决方案 > 设计无线传感器算法

arrays - 设计无线传感器算法

问题描述

所以我得到了一个包含 n >= 2 个整数的排序数组。这些整数用于表示无线传感器，每个传感器的广播半径为 2，这意味着如果我有一个数字“4”，它最多可以达到“2”或“6”。因此，我需要设计一种算法，该算法返回一个数组，该数组包含所有可以相互通信的传感器对（作为子数组），它们的消息可能由某个中间传感器转发，例如。鉴于数组中存在“10”，“8”能够与“12”通信。该算法还需要在 O(n^2) 时间内运行。

所以起初它很简单，我只需获取数组的长度 n，然后使用 while 循环 (i < n) 遍历它，如果当前元素 + 2 大于或等于下一个元素，则添加它的索引和下一个元素对子数组的索引，并将其添加到一个空数组中。但是我遇到了中间传感器部分的问题。不过，我如何找到中间传感器连接？

标签： arraysalgorithmsorting

解决方案

  1. 对列表进行排序（需要O(NlogN)时间）
  2. 开始遍历数组
  3. 查看当前元素是否可以与我们当前的集合进行通信。如果是，则将其添加到集合中并继续。否则，存储旧集合，创建一个新集合并将当前元素添加到其中。
  4. 对于每组，生成所有可以通信的传感器对。

就像是：

def generate_pairs(array):
    pairs = []
    array_length = len(array)
    for i in range(0, array_length):
        for j in range(i+1, array_length):
            pairs.append([array[i],array[j]])
    return pairs

main_list = [1,2,4,7,9,10,13]
main_list.sort()
curr_set = [main_list[0]]
all_sets = []
for i in range (1,len(main_list)):
    if main_list[i]-main_list[i-1] <=2:
        curr_set.append(main_list[i])
    else:
        all_sets.append(curr_set)
        curr_set = [main_list[i]]

all_pairs = []
for i in all_sets:
    all_pairs += generate_pairs(i)

print(all_pairs)
# prints [[1, 2], [1, 4], [2, 4], [7, 9], [7, 10], [9, 10]]

推荐阅读