JS中的算法与数据结构之字典(Dictionary)实例详解

下面我将详细讲解“JS中的算法与数据结构之字典(Dictionary)实例详解”的完整攻略。

什么是字典？

字典是一种存储唯一键和对应值的数据结构，每个键对应一个值。JavaScript 中的对象就是字典的一种实现，通过键值对来存储和访问数据。

字典的操作

字典支持以下几种操作：

• 添加键值对
• 删除键值对
• 查找键值对
• 获取所有键
• 获取所有值

字典的实现

下面是使用 ES6 的 class 实现字典的代码：

class Dictionary {
  constructor() {
    this.items = {}; // 用对象来存储字典的键值对
  }

  // 添加键值对
  set(key, value) {
    this.items[key] = value;
  }

  // 删除键值对
  delete(key) {
    if (this.has(key)) {
      delete this.items[key];
      return true;
    }
    return false;
  }

  // 查找键值对
  has(key) {
    return key in this.items;
  }

  // 获取对应键的值
  get(key) {
    return this.has(key) ? this.items[key] : undefined;
  }

  // 获取所有键
  keys() {
    return Object.keys(this.items);
  }

  // 获取所有值
  values() {
    return Object.values(this.items);
  }

  // 获取字典的大小
  size() {
    return Object.keys(this.items).length;
  }

  // 清空字典
  clear() {
    this.items = {};
  }
}

示例说明

下面分别演示如何使用字典来实现两个常见的问题。

统计字符串中每个单词出现的次数

const str = 'the quick brown fox jumps over the lazy dog';
const words = str.split(' ');
const countMap = new Dictionary();

for (let word of words) {
  if (countMap.has(word)) {
    countMap.set(word, countMap.get(word) + 1);
  } else {
    countMap.set(word, 1);
  }
}

console.log(countMap.items); // { "the": 2, "quick": 1, "brown": 1, "fox": 1, "jumps": 1, "over": 1, "lazy": 1, "dog": 1 }

查找数组中第一个不重复的元素

function findFirstUnique(arr) {
  const freqMap = new Dictionary();

  for (let i = 0; i < arr.length; i++) {
    let num = arr[i];
    if (freqMap.has(num)) {
      freqMap.set(num, freqMap.get(num) + 1);
    } else {
      freqMap.set(num, 1);
    }
  }

  for (let i = 0; i < arr.length; i++) {
    let num = arr[i];
    if (freqMap.get(num) === 1) {
      return num;
    }
  }

  return undefined;
}

console.log(findFirstUnique([1, 2, 3, 2, 1, 4])); // 3
console.log(findFirstUnique([1, 1, 2, 2, 3, 4])); // 3
console.log(findFirstUnique([1, 1, 2, 2, 3, 3, 4, 4])); // undefined

以上就是“JS中的算法与数据结构之字典(Dictionary)实例详解”的完整攻略。