Comment vérifier si un tableau int est un tableau sortingé de manière circulaire?

J’ai un tableau entier, disons {1, 3, 4, 7, -9, 0} . Ce tableau est sortingé de manière circulaire , tandis que le tableau {2, 4, 9 , 3} n’est pas sortingé de manière circulaire.

Un tableau est sortingé de manière circulaire si ses éléments sont sortingés à l’exception d’une rotation.

Par exemple:

 4 5 6 7 1 2 3 

Les éléments ici, 1 2 3 4 5 6 7 , sont “en ordre”, mais ils sont tournés vers la gauche de trois. Donc, si nous tournons à droite de 3, nous obtenons 1 2 3 4 5 6 7 qui est un tableau sortingé.

Étant donné un tableau, comment pouvez-vous vérifier si le tableau est sortingé de manière circulaire?

Vous pouvez parcourir le tableau et vérifier que toutes les valeurs augmentent. Et dès que vous atteignez la première valeur qui n’augmente pas, vérifiez qu’elle et toutes les valeurs suivantes sont croissantes ET inférieures ou égales au premier élément du tableau.

Modifier:

Je pense que les gens négligent la solution de Daniel parce qu’ils ne la comprennent pas ou ne pensent pas qu’elle est cassée. C’est sortingste parce que je pense que sa solution est shinye.

 def is_circular_sorted(arr): count = 0 length = len(arr) for i in range(length): if arr[i] > arr[(i+1) % len(arr)]: count += 1 return count <= 1 In [4]: is_circular_sorted([1, 2, 3, 4]) Out[4]: True In [5]: is_circular_sorted([1, 1, 1, 1]) Out[5]: True In [6]: is_circular_sorted([1, 3, 4, 7, -9]) Out[6]: True In [7]: is_circular_sorted([1, 3, 4, 2]) Out[7]: False 

Pour un peu d'explication. Pour vérifier si une liste est sortingée en forme de cercle, ma réponse initiale indiquait que vous deviez vérifier qu'une ou plusieurs "ruptures" étaient complètement sortingées ET que tous les nombres après la "rupture" étaient inférieurs au premier chiffre du tableau.

Cependant, comme le montre la réponse de Daniel, vous n'avez pas besoin de vérifier TOUS les nombres après le "break", seul le dernier numéro (qui se trouve être le plus grand / maximum après la pause car ils sont sortingés).

Il devrait toujours y avoir une pause, à moins que la liste ne soit remplie avec les mêmes numéros, auquel cas il n'y aurait pas de coupure et le compte serait 0.

Au cas où certains utilisateurs se demanderaient à quoi ressemble l’implémentation.

 public boolean isCircularSorted(int[] array) { int size = array.length; int count = 0; for(int x=0; x array[(x+1)%size]) count ++; return (count <= 1); } 

Cela a également été mentionné par l'utilisateur Daniel.

Comme l’a dit @Daniel, en utilisant la value[i] > value[(i+1)%length] , s’il est true nous comptons 1, si le count à la fin est égal à 0 ou 1 , le array original est un array circulaire! Je pense que c’est un bon moyen !!