Created
October 12, 2024 10:58
-
-
Save youssef3wi/a17fe12e44422c222dba38e8c5890b9c to your computer and use it in GitHub Desktop.
Implémentez la méthode smallestInterval(numbers) qui retourne le plus petit intervalle positif entre deux éléments du tableau numbers.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.security.SecureRandom; | |
| import java.time.Duration; | |
| import java.time.Instant; | |
| import java.util.ArrayList; | |
| import java.util.List; | |
| import java.util.Random; | |
| import static java.lang.System.nanoTime; | |
| import static java.util.Arrays.asList; | |
| /** | |
| * Implémentez la méthode {@link #smallestInterval(List)} qui retourne <b>le plus petit intervalle | |
| * positif entre deux éléments</b> du tableau {@code numbers}. | |
| * <p> | |
| * Par exemple, si on considère le tableau {@code [1, 6, 4, 8, 2]}, le plus petit intervalle est {@code 1} | |
| * (différence entre {@code 2} et {@code 1}) | |
| * <p> | |
| * Contraintes: | |
| * <ul> | |
| * <li>{@code numbers} contient au moins deux éléments et au maximum 100 000 éléments.</li> | |
| * <li>La solution qui privilégie la vitesse d'éxecution pour les tableaux de grande taille | |
| * obtiendra le plus de points.</li> | |
| * <li>La différence entre deux éléments ne dépassera jamais la capacité d'un entier | |
| * pour votre langage.</li> | |
| * </ul> | |
| */ | |
| public class SmallestInterval { | |
| private static int smallestInterval(List<Integer> numbers) { | |
| int smallest = Integer.MAX_VALUE; | |
| int[] sortedNumbers = numbers.stream().mapToInt(Integer::intValue).sorted().toArray(); // sort ascending | |
| for (int idx = 0; idx < sortedNumbers.length; idx++) { | |
| if (idx + 1 == sortedNumbers.length) { | |
| break; // can't calculate diff | |
| } | |
| for (int jdx = idx + 1; jdx < sortedNumbers.length; jdx++) { | |
| int diff = sortedNumbers[jdx] - sortedNumbers[idx]; // sorted | |
| if (diff == 0) { | |
| return 0; | |
| } | |
| if (diff < smallest) { | |
| smallest = diff; | |
| } | |
| } | |
| } | |
| return smallest; | |
| } | |
| public static void main(String[] args) { | |
| System.out.println("Input = [1, 3, 9]"); | |
| long current = nanoTime(); | |
| System.out.printf("Output in %.3fms = %s%n", (nanoTime() - current) / 1E6, smallestInterval(asList(1, 3, 9))); | |
| System.out.println("----------------------------"); | |
| Random random = new SecureRandom(); | |
| List<Integer> numbers = new ArrayList<>(); // fill data | |
| for (int idx = 0; idx < 99999; idx++) { | |
| numbers.add(random.nextInt(99999) + 1); | |
| } | |
| System.out.println("Input = 99999 elements"); | |
| Instant start = Instant.now(); | |
| int result = smallestInterval(numbers); | |
| float duration = Duration.between(start, Instant.now()).toMillis(); | |
| System.out.printf("Output in %.2fs = %s%n", duration / 1E3, result); | |
| System.out.println("----------------------------"); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment