Je travaille à Java. J'ai une liste non ordonnée de 5 chiffres allant de 0 à 100 sans répétitions. Je voudrais détecter si 3 des numéros sont séquentiels sans intervalle.
Exemples: P>
[9,12,13,11,10] true [17,1,2,3,5] true [19,22,23,27,55] false
7 Réponses :
algorithme très naïf (mais plus rapide): (votre matrice est entrée [], en supposant que cela ne contient que 0-100 numéros comme vous l'avez dit)
int[] nums=new int[101];
for(i=0;i<N;i++)
{
int a=input[i];
nums[a]++;
if (a>0) { nums[a-1]++; }
if (a<100) { nums[a+1]++; }
}
Vous oblige à boucler à travers un tableau de 100 Taille.
Si quelqu'un se demande pourquoi ce n'est pas la réponse sélectionnée, j'ai testé et choisi la réponse la plus rapide. J'apprécie cependant la réponse.
Allouer une matrice de taille 100:
private static final int MAX_VALUE = 100;
public boolean hasSequence(int [] values) {
int [] bigArray = new int[MAX_VALUE];
for(int i = 0; i < values.length; i++) {
bigArray[values[i]] = 1;
}
for(int i = 0; i < values.length; i++) {
index = values[i];
if(index == 0 || index == MAX_VALUE-1) {
continue;
}
if(bigArray[index-1] == 1 && bigArray[index+1] == 1) {
return true;
}
}
return false;
}
Non, c'est un pseudocode lisible qui arrive à ressembler à une autre langue que je puisse penser. C'est aussi la seule approche jusqu'à présent qui est O (nombre d'articles de la liste) et fonctionnerait même s'il y avait des duplicats.
Je suis allé de l'avant et je l'ai remplacé avec une forme Java et j'ai éloigné le petit tableau.
Cette solution lancera une exception d'index hors limites dans la deuxième boucle. De plus, ne devriez pas la deuxième boucle de boucle à travers l'INT dans les valeurs, pas l'INT entre 0 et sa taille?
Je crois que la ligne 7 devrait lire si (bigarray [valeurs [i] -1] == 1 && bigarray [valeurs [i] +1] == 1) Mais avant cela, il faut vérifier à Assurez-vous que des valeurs [i]! = 0. Si cette réponse est modifiée pour résoudre ce problème, ce sera la réponse acceptée car je pense que c'est le plus rapide tout en étant très clair.
@Rroudryar merci, a nettoyé cela. Il n'y a pas de réel besoin de vérifier que les valeurs [index]! = 0 cependant.
Si index = 0 ou index = BIGARRAY.LENGTHE - 1, alors cela lancera une exception.
Merci, ajouté cette contrainte.
Merci, c'est la solution la plus rapide.
Ce code semble mettre en œuvre vos exigences:
public class OrderdedList {
public static void main(String[] args) {
System.out.println(orderedWithNoGap(Arrays.asList(9, 12, 13, 11, 10))); // true
System.out.println(orderedWithNoGap(Arrays.asList(17,1,2,3,5))); // true
System.out.println(orderedWithNoGap(Arrays.asList(19,22,23,27,55))); // false
}
private static boolean orderedWithNoGap(List<Integer> list) {
Collections.sort(list);
Integer prev = null;
int seq = 0;
for(Integer i : list) {
if(prev != null && prev+1 == i)
seq = seq == 0 ? 2 : seq+1;
prev = i;
}
return seq >= 3;
}
}
Avez-vous couru ceci? Arrays.Aslist () Renvoie une liste Immutable
@Lukaseder Oui, j'ai fait. Statique publique
@LukaSeder Il renvoie une liste de la taille fixe qui est pas java.util.arraylist . Vous ne pouvez pas ajouter () à celui-ci et vous ne pouvez pas supprimer () à partir de celui-ci, mais vous pouvez appeler set () , donc Les mutations en place sont correctes.
Ce n'est pas un java.util.arraylist , c'est un java.util.arys.arraylist . Mais j'avais tort, ce n'est pas immuable. C'est juste une liste de taille fixe. Wow, appris quelque chose aujourd'hui! (après toutes ces années...)
Nécessite une sorte que l'OP semblait impliquer qu'il ne voulait pas.
Si je devais l'écrire maintenant, je vais probablement aller avec l'approche la plus naïve de commander les chiffres ... , parfois les solutions les plus simples sont les meilleures :)
En effet, je ne suis pas opposé au tri si c'est la solution la plus efficace; Cependant, je soupçonne intuitivement que ce n'est pas le cas. Dans ce cas, il existe définitivement des solutions plus rapides (bien que la réponse soit évidemment appréciée).
Algorithme général Étapes.
int[] arr = {9,12,13,11,10};
BitSet numbers = new BitSet(101);
for (int no : arr) {
numbers.set(no);
}
int sequenceCount = 0;
int last = -10;
for (int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1)) {
if (sequenceCount == 0 || i - last > 1) {
sequenceCount = 1;
} else {
sequenceCount++;
if (sequenceCount >= 3) {
System.out.println("Sequence start: " + (last - 1));
break;
}
}
last = i;
}
System.out.println("Done");
L'OP a déjà dit qu'il avait une solution en utilisant une sorte, mais cherchait une solution n'utilisant pas une sorte.
AS OP souligné dans Comment , Il veut vérifier si la liste contient 3 numéros séquentiels ou plus
public class WarRoom {
static final int seqCount = 3;
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>((Arrays.asList(9, 11, 123, 511, 10)));
for (int i : list) {
if (seqNumbers(list, i, 0) >= seqCount) {
System.out.println("Lucky Numbers : " + (i++) + "," + (i++) + "," + i);
}
}
}
public static int seqNumbers(List<Integer> list, int number, int count) {
if (list.contains(number)) {
return seqNumbers(list, number + 1, count + 1);
}
else {
return count;
}
}
}
ne pas tester cela, mais pour une petite empreinte mémoire, vous pouvez utiliser un bitset
Cette réponse utilise Bitset avec un changement de bits pour trouver des bits consécutifs dans un ensemble
Je ne comprends pas - comment est la première séquence
true ?Je pense que la question est, existe-t-il 3 chiffres pouvant être arrangés à être séquentiels sans intervalle.
@Pace: ah oui, ça doit être.
Le premier est celui-ci Oeis.org/a007305
ne ressemble pas à Apache.commons: D Suggestion: implémentez simplement votre algorithme comme vous l'avez mentionné. Trier et passer à travers, fixant un drapeau si 3 joints sont détectés
Une question concernant vos besoins, cela doit-il être exactement 3 éléments ou 3 éléments ou plus ?
Trois ou plus. C'est ce qui fait la première séquence
true .