daily pastebin goal
74%
SHARE
TWEET

Untitled

a guest Mar 19th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Given an array of integers, find the first missing positive integer in linear time and constant space.
  3. In other words, find the lowest positive integer that does not exist in the array.
  4. The array can contain duplicates and negative numbers as well.
  5.  
  6. For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
  7.  
  8. You can modify the input array in-place.
  9. */
  10. function findSmallestMissingPositiveInteger(arr) {
  11.   // Il numero può essere al massimo arr.length + 1,
  12.   // quando nell'array ci sono tutti e soli i numeri compresi tra 1 ed arr.length
  13.   // in qualsiasi altro caso ci sarà un gap prima di tale valore.
  14.  
  15.   // Quindi possiamo scartare tutti i numeri al di fuori del range [1, arr.length], mettendoli a 0
  16.   for (let i = 0; i < arr.length; ++i) {
  17.     if (arr[i] < 1 || arr[i] > arr.length) {
  18.       arr[i] = 0;
  19.     }
  20.   }
  21.  
  22.   // Adesso possiamo semplicemente ciclare e trattare i numeri come indici all'array stesso
  23.   // e il principio di base è: esploro e marchio le celle come libera (0) o occupata (-1)
  24.   for (let i = 0; i < arr.length; ++i) {
  25.     // Ciclo finché non trovo il primo numero valido
  26.     if (arr[i] !== 0 && arr[i] !== -1) {
  27.       // Mi salvo il valore
  28.       let curr = arr[i];
  29.       // Marchio la cella come libera
  30.       arr[i] = 0;
  31.  
  32.       while (true) {
  33.         // Prendo il valore successivo
  34.         let next = arr[curr - 1];
  35.         // Segno la posizione come occupata
  36.         arr[curr - 1] = -1;
  37.         // Finchè la cella di destinazione non è già marchiata come libera (0) o occupata (-1)
  38.         // devo continuare a propagare l'esplorazione seguendo la catena di indici
  39.         // altrimenti non so dove mettere il valore appena estratto.
  40.         if (next === 0 || next === -1) {
  41.           break;
  42.         }
  43.         curr = next;
  44.       }
  45.     }
  46.   }
  47.  
  48.   // Cerco la prima cella libera, che corrisponde al gap nella sequenza di valori
  49.   for (let i = 0; i < arr.length; ++i) {
  50.     if (arr[i] === 0) {
  51.       return i + 1;
  52.     }
  53.   }
  54.  
  55.   // Se non ho trovato nessun gap la soluzione è il primo intero maggiore della lunghezza dell'array
  56.   return arr.length + 1;
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top