Структура данных в JavaScript, которая поддерживает Insert, Remove и GetRandomElement

Я наткнулся на этот вопрос из интервью и хотел найти для него решение на JavaScript (а не на Java или C++):

Реализуйте структуру данных, подобную набору, которая эффективно поддерживает Insert, Remove и GetRandomElement. Пример: если вы вставляете элементы 1, 3, 6, 8 и удаляете 6, структура должна содержать [1, 3, 8]. Теперь GetRandom должен возвращать одно из 1, 3 или 8 с равной вероятностью.

Здесь на Java дан ответ: Структура данных: вставить, удалить, содержать, получить случайный элемент, все за O(1) Однако он не предлагает пример кода. Я новичок и только учусь использовать хеш-таблицы, поэтому, если вы можете дать объяснение кода, я был бы признателен!


javascript hashtable
person CharStar    schedule 05.01.2017    source источник
comment
javascript имеет структуру данных для наборов в ES6, кроме этого вы можете использовать массив. Хеш-таблица должна соответствовать объекту или карте, и я не думаю, что она подходит для этой работы.   -  person maioman    schedule 05.01.2017

Ответы (4)


arrow_upward
2
arrow_downward

Вот два простых решения:

Первый:

var RandomizedSet = function() {
    this.values = [];
};

RandomizedSet.prototype.insert = function(val) {
    if (this.values.includes(val)) return false;
    this.values.push(val);
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    const idx = this.values.indexOf(val);
    if (idx === -1) return false;
    this.values.splice(idx,1);
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    return this.values[Math.floor(Math.random() * this.values.length)]  ;
};

Второй:

var RandomizedSet = function() {
    this.values = {};
    this.length = 0;
};

RandomizedSet.prototype.insert = function(val) {
    if (this.values[val] !== null && this.values[val] !== undefined) return false;
    this.values[val] = val;
    this.length++;
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    if (this.values[val] === null || this.values[val] === undefined) return false;
    delete this.values[val];
    this.length--;
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    return Object.keys(this.values)[Math.floor(Math.random() * this.length)]  ;
};
person Abhineet Kandele    schedule 13.06.2020
comment
Хороший. Вы можете улучшить это, используя встроенный фрагмент кода Stack Overflow. Вы должны быть в состоянии обеспечить вызовы этих функций, чтобы показать примеры. Также сравните временные сложности каждой из функций в обеих версиях. - person Rahul Bhobe; 13.06.2020

arrow_upward
1
arrow_downward

Вы можете использовать объект JavaScript.

Создайте объект: var testObject = {};

  1. Вставить пару ключ/значение

testObject["keyName"] = "value here"; or testObject.keyName = "value here";

  1. Удалить ключ

delete testObject["keyName"];

  1. Получить случайный

    function pickRandomProperty(object) {
 var keys = Object.keys(object);

 if(keys.length > 0){
    return keys[Math.floor(keys.length * Math.random())];
 }
 else{
    return false;
 }
}

    Это вернет случайный ключ, который вы затем можете использовать для получения значения: testObject[randomKey]

person jakecyr    schedule 05.01.2017

arrow_upward
0
arrow_downward

Предположим, у нас есть следующие предположения:

  • Object.keys имеет не постоянную сложность.
  • Иметь постоянную сложность: array.pop(), object[key], delete object[key], Math.floor(n)

Одним из решений является отслеживание всех элементов массива и их индексов в объекте. Делая это, мы можем удалить элемент, поменяв местами его и последний, а затем использовать функцию всплывающего окна, предполагая, что он имеет постоянную сложность.

'use strict'

function SetStructure () {
  this._length = 0
  this._obj = {}
  this._arr = []
}

SetStructure.prototype.remove = function (el) {
  const idx = this._obj[el]
  if (typeof idx !== 'number') {
    return false
  }
  delete this._obj[el]
  this._arr[idx] = this._arr[this._length-1]
  this._length--
  this._arr.pop()
  return true
}

SetStructure.prototype.insert = function (el) {
  const idx = this._obj[el]
  if (typeof idx === 'number') {
    return false
  }
  this._obj[el] = this._length++
  this._arr.push(el)
  return true
}

SetStructure.prototype.getRandom = function () {
  return this._arr[Math.floor(Math.random() * this._length)]
}


let s = new SetStructure()
s.insert(1)
s.insert(3)
s.insert(6)
s.insert(8)
s.remove(6)
person L. Meyer    schedule 05.01.2017

arrow_upward
0
arrow_downward

В итоге я сделал это, создав заданную структуру данных:

function Set() {

    let items = {};

    this.add = function(value) {
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };

    this.delete = function(value) {
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };

    this.has = function(value) {
        return items.hasOwnProperty(value);
    };

    this.values = function() {
        let values = [];
        for (let i = 0, keys = Object.keys(items); i < keys.length; i++) {
            values.push(items[keys[i]]);
        }
        return values;
    };

    this.getRandomElement = function() {
        var keys = Object.keys(items);
        return items[keys[Math.floor(Math.random() * keys.length)]];
    };
}

Протестировано соответственно:

let set = new Set();

set.add(1);
set.add(3);
set.add(6);
set.add(8);
console.log(set.values()); 
    // [1, 3, 6, 8];
set.delete(6);
console.log(set.values()); 
    // [1, 3, 8];
console.log(set.getRandomElement());
person CharStar    schedule 05.01.2017