élément K-ième N * N somme vecteur

Question

J'ai un vecteur unsorted V , |V| = N et je dois trouver l'élément K-th dans le vecteur Sorted

S = {V[i] + V[j] | 0 <= i,j < N}, |S| = N*N

Je pensais à trier par ordre croissant V puis calculer seulement le premier K éléments de S ou trier par ordre décroissant et calculer (N * N) - K si K > (N * N)/2 mais pour

N = 50.000 and K = 2.265.604.247

cela prend 0.2sec en Java juste pour itérer de 1 à N*N-K et j'ai besoin de le faire en 0.3sec max. Quelqu'un peut me donner un indice sur la façon de faire cela?

Answer 1

Ceci est mon idée de la solution.
Je pense que cela devrait être beaucoup plus rapide que de tout calculer, et que vous devriez le considérer.

---

V est triée la longueur du vecteur n, et nous voulons trouver k le plus grand nombre de produit cartésien de VxV = {v1+v2|,v1,v2∈V}.

Nous allons utiliser la méthode de recherche similaire à la recherche binaire pour trouver le nombre voulu.

Notez ceci:
Pour chaque numéro M, nous M = m+m, m < max{v|v∈ V} définir un ensemble X = {x ∈ VxV, x<=m+m=M}. Il est facile de trouver |X| et max{X} en utilisant ceci:

1. boucle à travers le V avec un indice i. Pour chaque v = V[i], v' = M-V[i]. En utilisant la recherche binaire, trouver l'index j ainsi: w = V[j] <= v' et j+1>n OR V[j+1] > v'.
2. Pour chaque bouclage avec i, additionnez tous les chiffres j calculés. Ce sont les éléments de numéro dans X.
3. max{X} est la plus grande valeur de v+w calculée pour chaque paire de i et j, donc vous devez vous en souvenir aussi.

En sélectionnant des valeurs différentes de M (utiliser la méthode de recherche binaire), vous pouvez trouver la valeur de M pour laquelle |X| = k. Lorsque vous l'avez trouvé, max{X} est votre solution.

---

PS. J'ai supprimé ma réponse précédente car elle contenait une partie que je croyais avoir supprimée, et parce que je l'ai écrite pour des multiplications d'éléments de V au lieu d'ajouts. Désolé pour le dérangement, n'importe qui.