DIV CSS 佈局教程網

字串去重複字元的兩種實作:JavaScript 雜湊法與 Python 一行寫法
編輯:關於JavaScript     

把字串中重複出現的字元去掉,只留第一次出現的那個,是練習演算法與資料結構的經典小題。雖然實務上機會不多,但它很適合拿來熟悉「以空間換時間」的雜湊思路。

JavaScript 版本:用物件當雜湊表

核心想法是邊掃描邊記錄。準備一個物件當成雜湊表,走訪字串的每個字元,若沒見過就記下並收集起來,見過就跳過。

function dropRepeat(str) {
  var result = "";
  var hash = {};
  for (var i = 0; i < str.length; i++) {
    var elem = str[i];
    if (!hash[elem]) {
      hash[elem] = true;
      result += elem;
    }
  }
  return result;
}

使用方式:

dropRepeat("abcdd"); // "abcd"
dropRepeat("aabbccabc"); // "abc"

時間複雜度是 O(n),額外使用了 O(k) 的空間(k 為不同字元數)。相比用 indexOf 暴力查找的 O(n²) 寫法,資料量一大差異就很明顯。

若使用 ES6,可以寫得更簡潔:

const dropRepeat = str => [...new Set(str)].join("");
// 或者保留原順序的 reduce 寫法
const dropRepeat2 = str =>
  [...str].filter((c, i) => str.indexOf(c) === i).join("");

Set 的底層同樣是雜湊,且天生去重,程式碼短很多。要注意 Set 會連帶改變型別判斷規則(例如 1 與 "1" 視為不同元素),對純字元處理沒有影響。

Python 版本

Python 有個很漂亮的寫法,利用 enumerate 搭配 index:只保留「第一次出現位置等於目前索引」的字元。

# -*- encoding:utf-8 -*-
string = 'abc123456ab2s'
r = ''.join(x for i, x in enumerate(string) if string.index(x) == i)
print string
print r

輸出結果:

abc123456ab2s
abc123456s

這個寫法直覺好讀,但 string.index 每次都要重新搜尋,整體仍是 O(n²)。若要處理大量資料,改用集合會快得多:

seen = set()
r = ''.join(c for c in string if not (c in seen or seen.add(c)))

兩種語言的對照

無論哪種語言,解這類問題的關鍵都在於「如何快速判斷某元素是否已出現」。用陣列的 indexOf 是線性搜尋,用雜湊表或集合則接近常數時間。這正是雜湊結構最典型的價值所在。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved