c# - 找到最小索引的最有效方法，其中它的值减去先前索引的值小于给定的 x？

Question

我有五个长整数 p、q、s、m 和 x。数组 numbers[] 由以下公式创建。

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

数字 (numbers[0]) 的第一个值是 s。

找到索引 j 的最有效方法是什么 i < j和 |numbers[j] - numbers[i]| <= x或 |numbers[j] - numbers[i]| >= m-x .

例如，在 p = 3, q= 7, s= 1, m= 29 en x= 1 的情况下，数组将是:

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

在这种情况下，索引 j 将为 3，因为 numbers[3] - numbers[0]<=x , 因为 x 是 1。

我考虑过使用诸如计数排序或基数排序的变体之类的东西，但我什么都做不了。

Answer 1

因为 i < j，那么你需要保证数字的长度至少为 2。

您可以执行两个嵌套循环，外部循环的范围从 j = 1 到 numbers.Length - 1(将可能的解决方案授予最小 j)到 i = 0 到 i < j。

然后根据您的规范比较两个位置。如果为真，则返回 j。如果它完成了两个循环，则没有解决方案。

编辑:代码示例

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
}