Javascript - обнаружение, что первый элемент появляется в отсортированном массиве, а также в другой несортированной коллекции

Question

У меня есть массив несортированных номеров и другой массив отсортированных номеров, например

const unSortedArray = [54, 23, 55, 76, 9, 11];
const sortedArray= [1, 2, 3, 4, ...., 100]

Как я могу узнать, что first element появляется в моем sortedArray, который также должен быть элементом, существующим в мой unSortedArray? В вышеприведенном примере должно возвращаться 9, потому что 9 существовало в unSortedArray, а также располагалось перед другим элементом в sortedArray

Обратите внимание, я использовал 1, 2, 3, 4 в моем примере выше, но мой пример из реального мира было не число, а GUID , скажем, мы не можем применить метод сортировки к unSortedArray, а затем выбрать первый элемент.

Я думал о объединении обоих массивов, но как объединить оба, не прерывая сортировку в sortedArray?

Вот пример

1) вывод должен быть 1, потому что даже элементы 1, 2, 9 и 10 существуют в обоих массивах , 1 имеет порядок порядка 2, 9, 10 в sortedArray

const unSortedArray = [54, 23, 55, 76, 9, 10, 2, 1]; 
const sortedArray= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 

2) вывод должен быть 9, потому что четный элемент 9 и 10 существует в обоих массивах, 9 имеет порядок выше 10 в sortedArray

const unSortedArray = [54, 23, 55, 76, 10, 9]; 
const sortedArray= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 

3) вывод должен быть '', поскольку в отсортированном массиве нет элементов в unSortedArray

const unSortedArray = [54, 23, 55, 76, 11]; 
const sortedArray= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 

Answer 1

Вы можете создать Set из unSortedArray и использовать set.has() в своем предикате для sortedArray.find():

const unSortedArray = [54, 23, 55, 76, 9, 11];
const sortedArray= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const setHasValue = set => value => set.has(value);
const firstElement = sortedArray.find(setHasValue(new Set(unSortedArray)));

console.log(firstElement);

Answer 2

Быстрый и грязный способ сделать это с помощью для l oop:

const unSortedArray = [54, 23, 55, 76, 9, 11];
const sortedArray= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

let firstVal;
for (i = 0; i < sortedArray.length; i++) {
  if (unSortedArray.includes(sortedArray[i])) {
    firstVal = sortedArray[i];
    break;
  }
}

console.log(firstVal);

Answer 3

Было бы неплохо создать таблицу поиска для несортированных элементов массива. Например,

{ 54: true
, 23: true
, 55: true
.
.
  11: true
}

Это будет задача O (k), где k - количество элементов в несортированном массиве. Затем find первый элемент в отсортированном массиве, который возвращает true. Это должна быть задача O (n), где n - количество элементов отсортированного массива. Дает решение по линейному времени.

Это должно сделать это.

function getFirst(usa,sa){
  var h = usa.reduce((r,n) => (r[n] = true, r), {});
  return sa.find(n => h[n]);
}

var r = getFirst([54,23,55,76,9,11], Array.from({length:100}, (_,i) => i+1));
console.log(r);