Блог

Я только что закончил работу над проблемой с литкодом, Нашел все дубликаты в массиве и у меня возникли некоторые вопросы о сложности проблемы с пространством. Эта проблема конкретно требует сложности пространства O(1). Ниже я написал четыре различных способа решения этой проблемы, но я не уверен, какова пространственная сложность каждого из этих вариантов.

Четыре варианта, которые я придумал, были:

1. Создайте массив результатов и сохраните в нем повторяющиеся числа. Затем верните этот массив. Я считаю, что это O(n), потому что мне нужен дополнительный массив.
2. Отфильтруйте массив nums и сохраните его в переменной nums. Я не уверен, является ли это O(1) или O(n), поскольку сейчас я создаю новый массив, но затем сразу же заменяю свой исходный.
3. Отфильтруйте массив nums и немедленно верните новый массив.
4. Используйте пользовательскую функцию filterInPlace, чтобы изменить размер массива nums. Я считаю, что это O(1), но это немного хлопотно-писать для проблемы с литкодом.

Я был бы признателен за некоторую ясность в этом вопросе. Спасибо!

 const findDuplicates = (nums) => {
  
  const swap = (i, j) => {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  };
  
  let i = 0;
  let idx;
  const n = nums.length;
  
  while (i < n) {
    
    idx = nums[i] - 1;
    
    if (nums[i] !== nums[idx]) {
      swap(i, idx);
    } else {
      i  = 1;
    }
  }
  
  // Option 1 - Use a results array to contain duplicates
  const result = [];
  for (let i = 0; i < n; i  = 1) {
    if (nums[i] !== i   1) {
      result.push(nums[i]);
    }
  }
  return resu<

  // Option 2 - Filter out duplicates and save in nums, then return nums
  nums = nums.filter((num, i) => num !== i   1);
  return nums;

  // Option 3 - Return the new array returned from Array.filter
  return nums.filter((num, i) => num !== i   1);

  // Option 4 - Write a filterInPlace function to modify array in place
  const filterInPlace = (array, condition) => {

    // The number of items that have been kept
    let j = 0;
    
    for (let i = 0; i < array.length; i  = 1) {
      if (condition(array[i], i)) {
        array[j] = array[i];
        j  = 1;
      }
    }
   
    array.length = j;
    return array;
  }

  filterInPlace(nums, (num, i) => num !== i   1);
  return nums;

}
 

1. Пространство будет наверняка O(n) .
2. и 3. Оба они одинаковы , вы можете напрямую вернуть их или назначить новой переменной , а затем вернуть ее. Array.filter возвращает новый массив требуемых элементов, который также O(n) является пространством для вновь сформированного массива .

4. Это происходит O(1) потому, что вы просто изменяете nums массив