Самое маленькое целое число, при котором будет последовательность натуральных чисел [закрыт]

105

04 октября 2019, 11:10

Есть массив

[4,3,6]

здесь самое маленькое целое число это - 5, при котором у нас будет массив

[3,4,5,6]

который последовательность натуральных чисел.

Здесь-

[2,4,6,8]

самое маленькое целое число, который отсутствует это - 3

А здесь - 1

[-1,-2]

Нужно написать функцию JavaScript, который будет возвращать самое маленькое целое число, который отсутствует в массиве.

Еще примеры массивов и ответов - [-3,-4,-5]-1, [-1,-2,1,7,4]-2, [1,2,3,6,8]-4 и т.д.

У меня такая программа, который видимо не так уж правильный.

    function solution(x){ 
    let n; 
    let m; 
    let y=x.sort((a,b)=>a-b); 
    for (var i = 0; i < y.length; i++) { 
        if (y[i]>y[i-1]!=1) { 
          n = y[i]-y[i-1]; 
          let k = 1 
          if (n>=1) { 
              m = y[i-1]+k; 
          } 
          else { 
            return k 
          }          
        }  
      }  
      return m;    
    } 
    console.log(solution([-1,-2,1,3]))

Answer 1

function solution(arr) { 
  let a = arr.filter(n => n > 0) 
    .sort((a, b) => a-b) 
    .reduce((acc, n, i, arr) => { 
      if (arr[i] != arr[i + 1]) { 
        acc.push(arr[i]) 
      }  
      return acc; 
    }, []); 
  for (let i = 0; i < a.length; i++) { 
    if (a[i] + 1 != a[i+1]) return a[i] + 1; 
  } 
  return 1; 
} 
 
console.log(solution([4, 3, 6])); // 5 
console.log(solution([2, 4, 6, 8])); // 3  
console.log(solution([-1, -2])); // 1 
console.log(solution([-3, -4, -5])); // 1 
console.log(solution([-1, -2, 1, 7, 4])); // 2 
console.log(solution([1, 2, 3, 6, 8])); // 4 
console.log(solution([2, 2])); // 3 
console.log(solution([2, 2, 3])); // 4

Надо заметить, что тут используется сомнительная практика обращения к элементам массива за пределами этого массива. Лучше так не делать. :)

Answer 2

Для начала создаем список с числами больше 0, а потом рекурсивно ищем минимальное число. Решение не требует сортировки и работает за время O(n)

const findMinNumber = (list, min) => { 
  if (!list[min]) return 1; 
  if (list[min].next) { 
    return findMinNumber(list, list[min].next); 
  } 
  return min + 1; 
}; 
 
const solution = (arr) => { 
  let min = Infinity; 
  const list = {}; 
  for (const number of arr) { 
    if (number > 0) { 
      if (number < min) { 
        min = number; 
      } 
      list[number] = {}; 
      if (list[number - 1]) { 
        list[number - 1].next = number; 
      } 
      if (list[number + 1]) { 
        list[number].next = number + 1; 
      } 
    } 
  } 
  return findMinNumber(list, min); 
} 
 
console.log(solution([4, 3, 6])); // 5 
console.log(solution([2, 4, 6, 8])); // 3  
console.log(solution([-1, -2])); // 1 
console.log(solution([-3, -4, -5])); // 1 
console.log(solution([-1, -2, 1, 7, 4])); // 2 
console.log(solution([1, 2, 3, 6, 8])); // 4 
console.log(solution([2, 2])); // 3 
console.log(solution([2, 2, 3])); // 4