Struktur data dalam JavaScript yang mendukung Sisipkan, Hapus, dan GetRandomElement

Saya menemukan pertanyaan wawancara ini dan saya ingin menemukan solusinya dalam JavaScript (bukan Java atau C++):

Menerapkan struktur data seperti kumpulan yang mendukung Sisipkan, Hapus, dan GetRandomElement secara efisien. Contoh: Jika Anda memasukkan elemen 1, 3, 6, 8 dan menghapus 6, strukturnya harus berisi [1, 3, 8]. Sekarang, GetRandom harus mengembalikan salah satu dari 1, 3 atau 8 dengan probabilitas yang sama.

Ini dijawab di Java di sini: Struktur data: menyisipkan, menghapus, memuat, mendapatkan elemen acak, semuanya di O(1) Namun, ia tidak menawarkan kode contoh. Saya seorang pemula dan baru belajar cara menggunakan tabel hash jadi jika Anda dapat memberikan penjelasan tentang kodenya, saya akan sangat menghargainya!


javascript hashtable
person CharStar    schedule 05.01.2017    source sumber
comment
javascript memiliki struktur data untuk set di ES6, selain itu Anda bisa menggunakan array. Tabel hash harus sesuai dengan objek atau peta dan menurut saya itu tidak cocok untuk pekerjaan itu   -  person maioman    schedule 05.01.2017

Jawaban (4)


arrow_upward
2
arrow_downward

Berikut adalah dua solusi sederhana:

Pertama:

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)]  ;
};

Kedua:

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
Bagus. Anda dapat memperbaikinya dengan menggunakan cuplikan kode tertanam Stack Overflow. Anda harus dapat memberikan panggilan ke fungsi-fungsi ini untuk menunjukkan contoh. Bandingkan juga kompleksitas waktu dari masing-masing fungsi di kedua versi. - person Rahul Bhobe; 13.06.2020

arrow_upward
1
arrow_downward

Anda bisa menggunakan objek JavaScript.

Buat objek: var testObject = {};

  1. Masukkan pasangan kunci/nilai

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

  1. Hapus kunci

delete testObject["keyName"];

  1. Dapatkan Acak

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

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

    Ini akan mengembalikan kunci acak yang kemudian dapat Anda gunakan untuk mendapatkan nilai: testObject[randomKey]

person jakecyr    schedule 05.01.2017

arrow_upward
0
arrow_downward

Misalkan kita mempunyai asumsi berikut:

  • Object.keys memiliki bukan kompleksitas yang konstan.
  • Memiliki kompleksitas yang konstan: array.pop(), object[key], delete object[key], Math.floor(n)

Salah satu solusinya adalah dengan melacak semua elemen dalam array dan indeksnya dalam suatu objek. Dengan melakukan ini, kita dapat menghapus sebuah elemen dengan menukarnya dan yang terakhir, lalu menggunakan fungsi pop, dengan menganggapnya memiliki kompleksitas yang konstan.

'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

Saya akhirnya melakukan ini dengan membuat kumpulan struktur data:

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)]];
    };
}

Mengujinya sesuai:

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