Interviewstreet Triplet

Question

Possible en double:
interviewstreet Triplet challenge

Il y a un tableau d'entiers d qui ne contient pas plus de deux éléments de la même valeur. Combien de triples ascendants distincts (d[i] < d[j] < d[k], i < j < k) sont présents?

Format d'entrée:

La première ligne contient un nombre entier N désignant le nombre d'éléments dans le tableau. Ceci est suivi par une ligne unique contenant N entiers séparés par un espace sans leader/espaces de fin

Format de sortie:

un nombre entier unique qui désigne le nombre de croissant distinct triples présent dans le tableau

Contraintes:

N <= 10^5 

Chaque élément du tableau est présen t au plus deux fois

Chaque élément de la matrice est un entier positif de 32 bits

entrée de l'échantillon:

6 

1 1 2 2 3 4 

sortie de l'échantillon:

4 

Explication :

Les triplés sont distincts

(1,2,3) 
(1,2,4) 
(1,3,4) 
(2,3,4) 

Answer 1

EDIT: Je suppose que les entiers ont reçu l'ordre, ce qui n'a pas été mentionné dans votre réponse. Avec des entiers non ordonnés, aucune optimisation n'est possible, vous devez utiliser l'approche de comptage de force brute. Si elles sont triées, continuez à lire.

---

Cela étant, vous n'avez pas vraiment besoin de beaucoup de programmation ici. C'est plus un problème mathématique. Tout d'abord, peu importe s'il y a 1, 2 ou plusieurs occurrences d'un nombre entier. Les triplets qui en résultent doivent être uniques de toute façon. Cela réduit à compter simplement combien d'entiers différents il y a dans le tableau. Nommez cette variable s.

Ensuite, nous appliquons simplement la formule suivante:

result = 0; 
for(first_index = 0; first_index < s; first_index++) { 
    for(second_index = first_index + 1; second_index < s; second_index++) { 
     result += s - second_index - 1; 
    } 
} 
return result; 

Cela peut cependant être simplifiée.Maintenant, si nous raisonnons sur les valeurs s - second_index - 1 prend pour une boucle externe, c'est juste la ligne de tous les entiers de 0 à s - 2 inversé! Ne sommes-nous pas heureux qu'il y ait une formule pour sa somme: où n est un entier, n * (n + 1)/2 est la somme des premiers entiers n.

Cela signifie que nous pouvons optimiser notre programme:

result = 0; 
for(first_index = 0; first_index < s; first_index++) { 
    result += (s - 2 - first_index) * (s - 2 - first_index + 1)/2; 
} 

Notez que nous pouvons encore simplifier à result = (x^3 - 3*x^2 + 2*x)/6.