Найти первую и последнюю позицию элемента в отсортированном массиве в порядке O (log n) - PullRequest
Новая
       11

Найти первую и последнюю позицию элемента в отсортированном массиве в порядке O (log n)

0 голосов
/ 12 марта 2020

Я делаю leetcode # 34

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Учитывая массив целых чисел, отсортированных в порядке возрастания, найти начальную и конечную позиции данного значение цели.

Сложность времени выполнения вашего алгоритма должна быть в порядке O (log n).

Если цель не найдена в массиве, вернуть [-1, -1].

Пример 1:

Входные данные: nums = [5,7,7,8,8,10], target = 8 Выходные данные: [3,4]

Пример 2:

Ввод: nums = [5,7,7,8,8,10], target = 6 Ввод: [-1, -1] 

var searchRange = function(nums, target) {
  var result = [];
  result[0] = findFirstIndex(nums, target);
  result[1] = findLastIndex(nums, target);

  return result;
};
//[5,7,7,8,8,10], target=10, midpoint=3
function findFirstIndex(nums, target) {
  var index = -1; //if cant find, return index=-1, will not execute below action
  var start = 0;
  var end = nums.length - 1;
  while (start <= end) {
    var midPoint = start + (end - start) / 2;
    if (nums[midPoint] >= target) {
      end = midPoint - 1;
    } else {
      start = midPoint + 1;
    }

    if (nums[midPoint] === target) {
      index = midPoint;
    }
  }
  return index;
}

function findLastIndex(nums, target) {
  var index = -1;
  var start = 0;
  var end = nums.length - 1;
  while (start <= end) {
    var midPoint = start + (end - start) / 2;
    if (nums[midPoint] <= target) {
      start = midPoint + 1; //[start,end]=[0,2]
    } else {
      end = midPoint - 1;
    }

    if (nums[midPoint] === target) {
      index = midPoint;
    }
  }
  return index;
}

Собственно, на этот ответ я ссылаюсь на метод Ника Уайта Java. Я думаю, что концепция должна быть правильной, но все еще не может выполнить ответ.

Может кто-нибудь знать почему? Спасибо.

Ответы [ 2 ]

1 голос
/ 12 марта 2020

Вам нужно округлить midPoint до целого числа, в противном случае вы попытаетесь получить доступ к дробным индексам. 

var searchRange = function(nums, target) {
  var result = [];
  result[0] = findFirstIndex(nums, target);
  result[1] = findLastIndex(nums, target);

  return result;
};

console.log(searchRange([5,7,8,8,8,10], 8));
console.log(searchRange([5,7,8,8,8,10], 10));

function findFirstIndex(nums, target) {
  var index = -1; //if cant find, return index=-1, will not execute below action
  var start = 0;
  var end = nums.length - 1;
  while (start <= end) {
    var midPoint = Math.floor(start + (end - start) / 2);
    if (nums[midPoint] >= target) {
      end = midPoint - 1;
    } else {
      start = midPoint + 1;
    }

    if (nums[midPoint] === target) {
      index = midPoint;
    }
  }
  return index;
}

function findLastIndex(nums, target) {
  var index = -1;
  var start = 0;
  var end = nums.length - 1;
  while (start <= end) {
    var midPoint = Math.floor(start + (end - start) / 2);
    if (nums[midPoint] <= target) {
      start = midPoint + 1; //[start,end]=[0,2]
    } else {
      end = midPoint - 1;
    }

    if (nums[midPoint] === target) {
      index = midPoint;
    }
  }
  return index;
}
0 голосов
/ 12 марта 2020

На самом деле нет необходимости в методе findLastIndex. Я немного изменил решение @ Barmar. 

    var searchRange = function(nums, target) {
    if(nums.length == 0) return [-1,-1];
    var result = [];
    var index = findFirstIndex(nums, target);
    result[0] = index;
    var value = nums[index];

    while(nums[index] === value){index++}

    result[1] = index - 1;

    return result;
};

При таком подходе я получил 48 ms, faster than 96.65% of JavaScript online submissions.

Это не улучшит общую сложность Big O, но, несомненно, улучшит сложность average-case.

...