查找总之数组第k个号码 [英] Find kth number in sum array

问题描述

给定一个数组A与N个元素我需要找到对（I，J），使得i不等于到j，如果我们写的总和A [I] + A [J]所有对（我， j）条然后它是在第k个位置。

Given an array A with N elements I need to find pair (i,j) such that i is not equal to j and if we write the sum A[i]+A[j] for all pairs of (i,j) then it comes at the kth position.

示例：设N = 4和数组A = [1 2 3 4]，如果K = 3，那么回答是5，我们可以看到它清楚那笔阵变成这样：[3 ，4,5,5,6,7]

Example : Let N=4 and arrays A=[1 2 3 4] and if K=3 then answer is 5 as we can see it clearly that sum array becomes like this : [3,4,5,5,6,7]

我不能对所有对i和j为N可以达到100000。请帮助如何解决这个问题

I can't go for all pair of i and j as N can go up to 100000. Please help how to solve this problem

我的意思是这样的：

int len=N*(N+1)/2;
int sum[len];
int count=0;
for(int i=0;i<N;i++){
   for(int j=i+1;j<N;j++){
        sum[count]=A[i]+A[j]; 
        count++;
   }
}
//Then just find kth element.

我们不能用这种方法去

推荐答案

下面是如何做到这一点（在伪code）。我现在已经证实，它工作正常。

Here is how to do it (in pseudo-code). I have now confirmed that it works correctly.

//A is the original array, such as A=[1,2,3,4]
//k (an integer) is the element in the 'sum' array to find

N = A.length

//first we find i
i = -1
nl = N
k2 = k
while (k2 >= 0) {
    i++
    nl--
    k2 -= nl
}

//then we find j
j = k2 + nl + i + 1

//now compute the sum at index position k
kSum = A[i] + A[j]

编辑： 现在我已经测试了这个工程。我不得不解决一些地方......基本上 K 输入参数应使用0的索引。 （该任择议定书似乎使用基于1的索引。）

I have now tested this works. I had to fix some parts... basically the k input argument should use 0-based indexing. (The OP seems to use 1-based indexing.)

编辑2： 我会尽力解释我的理论呢。我开始了之数组应该被想象成一个二维交错数组（宽随着高度的增加递减）的概念，用坐标（如提到的OP）是我和Ĵ。因此，对于一个数组，如[1,2,3,4,5]的之阵列将被认为是这样的：

EDIT 2: I'll try to explain my theory then. I began with the concept that the sum array should be visualised as a 2D jagged array (diminishing in width as the height increases), with the coordinates (as mentioned in the OP) being i and j. So for an array such as [1,2,3,4,5] the sum array would be conceived as this:

3,4,5,6,
5,6,7,
7,8,
9.

最上面一行是其中我将等于0，第二行的所有值是其中我等于1。找J我们做相同的，但在列方向的值。

The top row are all values where i would equal 0. The second row is where i equals 1. To find the value of 'j' we do the same but in the column direction.

...很抱歉我无法解释这更好！

... Sorry I cannot explain this any better!

这篇关于查找总之数组第k个号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！