Sắp xếp mảng chỉ chứa 3 giá trị duy nhất lặp lại trong JavaScript

Giả sử chúng ta có một mảng số chứa bất kỳ tần suất nào của đúng ba phần tử -1, 0 và 1 như sau:

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];

Chúng ta cần viết một hàm JavaScript nhận vào một mảng như vậy. Hàm nên đơn giản sắp xếp mảng đặc biệt này tại chỗ (in-place), tức là không dùng mảng phụ để lưu giá trị.

Điều kiện duy nhất là hàm của chúng ta phải là hàm thời gian tuyến tính (chỉ dùng một lần duyệt).

Ví dụ

Dưới đây là mã nguồn:

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1]; const sortSpecialArray = (arr = []) => {    const swap = (a, b) => {       let middle = arr[a]       arr[a] = arr[b]       arr[b] = middle    };    let left = 0;    let middle = 0;    let right = arr.length-1;    while(middle <= right){       if(arr[middle] === -1){          swap(left++, middle++);       }else if(arr[middle] === 0){          middle++;       }else if(arr[middle] === 1){          swap(right--, middle);       }    }; }; sortSpecialArray(arr); console.log(arr);

Kết quả

Đầu ra trên console:

[    -1, -1, 0, 0, 0,    0, 1, 1, 1, 1,    1 ]

Giải thích: Đây là thuật toán Dutch National Flag (3-way partitioning) của Dijkstra. 3 con trỏ: left ranh giới -1, middle duyệt, right ranh giới 1. O(n) time, O(1) space, 1 pass.