最有效的方式寻找到其值减去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?

查看:145
本文介绍了最有效的方式寻找到其值减去previous指数的值大于一个给定的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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆