最有效的方式寻找到其值减去previous指数的值大于一个给定的x较小的最小索引？ [英] Most efficient way to find the smallest index where its value minus the value of a previous index is smaller than a given x?

问题描述

我有五个长整数P，Q，S，M和X。数组编号，[]是由下式建立。

I have five long integers p, q, s, m and x. An array numbers[] is created by the following formula.

numbers[0] = s;
for(int i=1; i<numbers.Length;i++){
    numbers[i] = (p * numbers[i-1] + q) % m;
}

第一个数字值（数字[0]）为s。

The first value of numbers (numbers[0]) is s.

什么是找到索引j最有​​效的方式，其中 I＆LT; Ĵ和 |号码[J] - 数字[I] | ＆LT; = X 或 |号码[J] - 数字[I] |方式＆gt; = M-X

What is the most efficient way to find index j where i < j and |numbers[j] - numbers[i]| <= x or |numbers[j] - numbers[i]| >= m-x.

有关实例，在的情况下，其中p = 3，Q = 7，S = 1，M = 29连接X = 1阵列将是：

For instance, in a case where p = 3, q= 7, s= 1, m= 29 en x= 1 the array will be:

号[0] = 1，数字[1] = 10，数字[2] = 8和数字[3] = 2

numbers[0] = 1, numbers[1] = 10, numbers[2] = 8 and numbers[3] = 2.

在这种情况下，指标j是3，因为号码[3] - 数字[0]＆LT; = X ，因为x是1。

In this case index j would be 3, because numbers[3] - numbers[0]<=x, because x is 1.

我想过用一些诸如计算排序或基数排序的一个变种，但我不能得到任何工作。

I thought about using something such as a variant of counting sort or radix sort but I can't get anything to work.

推荐答案

由于I＆LT; j时，您需要授予该数字具有至少2的长度。

As i < j, then you need to grant that numbers has a length of at least 2.

您可以做两个嵌套循环，外层一个范围从j = 1至numbers.Length - 1（授予可能的解决方案是最小的j）条至i = 0至i＆下;学家

You could do two nested loops, the outer one ranging from j = 1 to numbers.Length - 1 (granting the possible solution to be the smallest j) to i = 0 to i < j.

然后你按照比较规范的两个位置。如果为true，复位J。如果完成两个循环，那么就没有办法了。

Then you compare both positions according your specs. If true, return j. If it finishes both loops, then there is no solution.

编辑：code样品

public int GetSmallestIndex(long[] numbers, long x, long m)
{
    if (numbers.Length >= 2)
    {
        for (int j = 1; j < numbers.Length; j++)
        {
            for (int i = 0; i < j; i++)
            {
                long diff = Math.Abs(numbers[j] - numbers[i]); 
                if (diff <= x || diff >= m - x)
                    return j;
            }
        }
    }

    return -1; //If no solution is found, return -1 as convention
}

这篇关于最有效的方式寻找到其值减去previous指数的值大于一个给定的x较小的最小索引？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！