โครงสร้างข้อมูลใน JavaScript ที่รองรับ Insert, Remove และ GetRandomElement

ต่อไปนี้เป็นวิธีแก้ปัญหาง่ายๆ สองวิธี:

อันดับแรก:

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

คุณสามารถใช้วัตถุ JavaScript

สร้างวัตถุ: var testObject = {};

1. แทรกคู่คีย์/ค่า

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

2. ลบคีย์

delete testObject["keyName"];

3. รับแบบสุ่ม

   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]

สมมติว่าเรามีข้อสันนิษฐานเหล่านี้:

• 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)

ฉันลงเอยด้วยการสร้างโครงสร้างข้อมูลชุด:

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());