python - 根据没有元素重复的条件从列表中获取值对

Question

我有一个整数列表，例如: 1 3 4 4 9 7 10(元素个数在1到200000之间) 和一个整数变量 D，它位于 0 和 10^9 之间。 以5为例。

我需要计算列表中有多少对彼此之间的差异不大于变量 D 但棘手的部分是如果我取值为 1 的零元素和第一个元素值为3的元素(它们之间的差值满足条件)我不能再使用列表的这些元素。

例如，对于上面的序列，答案是 3 对:(1,3) (4,4) (7,9)

我写了一段代码，看起来是正确的，但我需要提示如何更改输入序列和变量 d 以输出错误答案的方式

    list_of_colors = [1, 3, 4, 4, 9, 7, 10]
    d = 5

    number_of_pairs = 0

    list_of_colors.sort() # the values in the list are not always sorted

    i = 0 
    while True:
        if i >= len(list_of_colors): 
            break
        if i != len(list_of_colors) - 1:  
            # if the number i in list and i+1 is the same or difference between them not greater than a variable d...
            if (int(list_of_colors[i]) == int(list_of_colors[i + 1])) or abs(int(list_of_colors[i]) - int(list_of_colors[i + 1])) <= d:
                #print list_of_colors[i]," ",list_of_colors[i + 1]
                number_of_pairs += 1 # increasing the number of the acceptable pairs  
                i += 2  # jump over two elements, we already counted them
                continue
        i += 1

    print number_of_pairs

我需要另一种算法来将它与我的算法在输入序列和变量 d 的各种范围内的结果进行比较

请提出你的想法

Answer 1

对于这个问题我有一个贪心的解决方案:

对输入序列进行排序。

解析排序后的序列如下:

For ith element in the sequence, 
  if |a[i+1]-a[i]| <= D, 
     then pair up the elements. Proceed to process i+2th element.
  else
     proceed to process i+1th element.