JavaScript30秒， 从入门到放弃之Array（五）

[hongmaoxiao]

sampleSize

Gets n random elements at unique keys from array up to the size of array.

Shuffle the array using the Fisher-Yates algorithm. Use Array.slice() to get the first n elements. Omit the second argument, n to get only one element at random from the array.

const sampleSize = ([...arr], n = 1) => {
  let m = arr.length;
  while (m) {
    const i = Math.floor(Math.random() * m--);
    [arr[m], arr[i]] = [arr[i], arr[m]];
  }
  return arr.slice(0, n);
};

从给定的数组中随机选出指定个数的数组元素。

用 Fisher-Yates 算法将数组洗牌（打乱顺序）。然后使用Array.slice() 来截取数组的前n个元素。如果省略第二个参数n，按n=1处理，即仅取一个随机元素。

➜  code cat sampleSize.js
const sampleSize = ([...arr], n = 1) => {
    let m = arr.length;
    while (m) {
        const i = Math.floor(Math.random() * m--);
        [arr[m], arr[i]] = [arr[i], arr[m]];
    }
    return arr.slice(0, n);
};

console.log(sampleSize([1, 2, 3], 2));
console.log(sampleSize([1, 2, 3], 4));

➜  code node sampleSize.js
[ 2, 1 ]
[ 1, 3, 2 ]

let m = arr.length;
while (m) {
  const i = Math.floor(Math.random() * m--);
  [arr[m], arr[i]] = [arr[i], arr[m]];
}

关键点是这个while循环，按数组初始长度m每次递减1循环，然后结合Math.floor和Math.random在m范围内生成一个随机索引。用该索引对应的数组元素与索引m-1（即未交换过的最后一个元素）对应数组元素交换位置。循环结束，数组洗牌成功。

return arr.slice(0, n);

最后返回被截取的前n个元素。

shuffle

Randomizes the order of the values of an array, returning a new array.

Uses the Fisher-Yates algorithm to reorder the elements of the array.

const shuffle = ([...arr]) => {
 let m = arr.length;
 while (m) {
   const i = Math.floor(Math.random() * m--);
   [arr[m], arr[i]] = [arr[i], arr[m]];
 }
 return arr;
};

对指定数组进行随机排序并返回排好序的新数组。

用 Fisher-Yates 算法将数组洗牌（打乱顺序）并返回排好序的新数组。

➜  code cat shuffle.js
const shuffle = ([...arr]) => {
    let m = arr.length;
    while (m) {
        const i = Math.floor(Math.random() * m--);
        [arr[m], arr[i]] = [arr[i], arr[m]];
    }
    return arr;
};

const foo = [1, 2, 3];
console.log(shuffle(foo));
console.log(foo);

➜  code node shuffle.js
[ 1, 3, 2 ]
[ 1, 2, 3 ]

这就是前面sampleSize用到的算法，注意的是返回的是新的数组，不是在原数组上进行排序的。

similarity

Returns an array of elements that appear in both arrays.

Use Array.filter() to remove values that are not part of values, determined using Array.includes().

const similarity = (arr, values) => arr.filter(v => values.includes(v));

返回一个包含两个数组的共同元素的数组。

使用Array.filter()结合Array.includes()把一个数组中不属于第二个数组values的元素都剔除。

➜  code cat similarity.js
const similarity = (arr, values) => arr.filter(v => values.includes(v));

console.log(similarity([1, 2, 3], [1, 2, 4]));
➜  code node similarity.js
[ 1, 2 ]

filter的主体是第一个数组arr，最终将不满足条件的元素剔除掉。那么不满足的条件又是什么呢？

v => values.includes(v)

条件是第一个数组arr不在第二个数组values里的所有元素，也即仅保留满足values.includes(v)的所有元素。

sortedIndex

Returns the lowest index at which value should be inserted into array in order to maintain its sort order.

Check if the array is sorted in descending order (loosely). Use Array.findIndex() to find the appropriate index where the element should be inserted.

const sortedIndex = (arr, n) => {
  const isDescending = arr[0] > arr[arr.length - 1];
  const index = arr.findIndex(el => (isDescending ? n >= el : n <= el));
  return index === -1 ? arr.length : index;
};

返回一个元素应该插入到已知排好序的数组并且不改变该数组排序方式的最小索引。

检查一个数组是否已经按降序排列（松散的），然后使用Array.findIndex()去找出指定的元素应该插在数组中合适位置的索引并返回。

➜  code cat sortedIndex.js
const sortedIndex = (arr, n) => {
  const isDescending = arr[0] > arr[arr.length - 1];
  const index = arr.findIndex(el => (isDescending ? n >= el : n <= el));
  return index === -1 ? arr.length : index;
};

console.log(sortedIndex([5, 3, 2, 1], 4));
console.log(sortedIndex([30, 50], 40));

➜  code node sortedIndex.js
1
1

之所以叫sortedIndex是因为数组已经排序了，但升序降序未知。为此只需比较数组第一个元素arr[0]和数组最后一个元素arr[arr.length - 1]的大小即可判断升降序。

const index = arr.findIndex(el => (isDescending ? n >= el : n <= el));

这里有一个三元运算表达式：

isDescending ? n >= el : n <= el

如果是降序的，判断数组arr元素el是否小于或者等于指定元素n，也就是说，当满足指定数组元素n首次大于或者等于arr遍历过程中任意一个元素el的时候，就返回此时的索引。否则判断数组arr元素el是否大于或者等于指定元素n，寻找过程与前边类似。

return index === -1 ? arr.length : index;

最后，判断所找索引index是否为-1，若是，说明n比arr所有元素要小，应该放在arr最后一位，即index = arr.length；否则直接返回索引index。

sortedIndexBy

Returns the lowest index at which value should be inserted into array in order to maintain its sort order, based on a provided iterator function.

Check if the array is sorted in descending order (loosely). Use Array.findIndex() to find the appropriate index where the element should be inserted, based on the iterator function fn.

const sortedIndexBy = (arr, n, fn) => {
 const isDescending = fn(arr[0]) > fn(arr[arr.length - 1]);
 const val = fn(n);
 const index = arr.findIndex(el => (isDescending ? val >= fn(el) : val <= fn(el)));
 return index === -1 ? arr.length : index;
};

返回一个元素应该插入到已知排好序的数组并且不改变该数组排序方式的最小索引，前提是受一个指定的方法支配。

检查一个数组是否已经按降序排列（松散的），然后使用Array.findIndex()去找出指定的元素应该插在数组中合适位置的索引并返回，前提是受一个指定的方法支配。

➜  code cat sortedIndexBy.js
const sortedIndexBy = (arr, n, fn) => {
  const isDescending = fn(arr[0]) > fn(arr[arr.length - 1]);
  const val = fn(n);
  const index = arr.findIndex(el => (isDescending ? val >= fn(el) : val <= fn(el)));
  return index === -1 ? arr.length : index;
};

console.log(sortedIndexBy([{ x: 3 }, { x: 4 }, { x: 5 }], { x: 4 }, o => o.x));

➜  code node sortedIndexBy.js
1

sortedIndexBy跟sortedIndex字面上只差一个By，一般而言By有基于xx的意思。

这里就是基于某个方法fn，意即在findIndex找合适元素的时候指的是对元素调用fn后的结果来进行比较，而不是元素本身。另外要注意的是，判断原数组arr升降序是也是fn调用结果的升降序，而不是元素本身的升降序。

sortedLastIndex

Returns the highest index at which value should be inserted into array in order to maintain its sort order.

Check if the array is sorted in descending order (loosely). Use Array.map() to map each element to an array with its index and value. Use Array.reverse() and Array.findIndex() to find the appropriate last index where the element should be inserted.

const sortedLastIndex = (arr, n) => {
 const isDescending = arr[0] > arr[arr.length - 1];
 const index = arr
   .map((val, i) => [i, val])
   .reverse()
   .findIndex(el => (isDescending ? n <= el[1] : n >= el[1]));
 return index === -1 ? 0 : arr.length - index - 1;
};

返回一个元素应该插入到已知排好序的数组并且不改变该数组排序方式的最大索引（从右边数的最小索引）。

检查一个数组是否已经按降序排列（松散的），然后使用Array.map()把原数组map一个包含索引和元素值的二维数组，在此map后的数组上用Array.findIndex()去找出指定的元素应该插在数组从右边数的合适位置的索引并返回。

➜  code cat sortedLastIndex.js
const sortedLastIndex = (arr, n) => {
    const isDescending = arr[0] > arr[arr.length - 1];
    const index = arr
        .map((v, i) => [i, v])
        .reverse()
        .findIndex(el => (isDescending ? n <= el[1] : n >= el[1]));

    return index === -1 ? 0 : arr.length - index;
};

console.log(sortedLastIndex([10, 20, 30, 30, 40], 30));

➜  code node sortedLastIndex.js
4

const index = arr
  .map((v, i) => [i, v])
  .reverse()
  .findIndex(el => (isDescending ? n <= el[1] : n >= el[1]));

首先用原数组arr去map一个二维数组，至于为什么一定要去map待会再讲。

然后reverse()去把map后的二维数组翻转。

最后在翻转数组基础上去查找对应索引:

// sortedLastIndex
isDescending ? n <= el[1] : n >= el[1]

// sortedIndex
isDescending ? n >= el : n <= el

这里不难看出sortedLastIndex和sortedIndex的三元运算表达式是不一样的。

• sortedLastIndex此时是对一个二维数组进行findIndex查找，二维数组的第二个元素即el[1]才是值，所以要跟它比较。
• sortedLastIndex的二维数组是经过翻转的，即如果本来数组是降序的，翻转后为升序，所以应该找元素n首次满足小于或等于数组元素el[1]的索引，而sortedIndex显然相反。

最终再对找出来的是索引index进行判断，如果index === -1，那么应该返回0，怎么讲？

对于-1来说，从右边数起，把整个数组数完了，都没有找到能放它的位置，那么只有数组第一个位置符合它。

如果index !== -1，也就是找到一个合适的索引，但是这个index是从右边数的，转换成从左边数的索引就是arr.length - index，（原文是arr.length - index - 1）我认为是错的。举个例子：

arr = [5, 4, 3, 3, 2, 1]
要把3插入数组arr的从右边数是2；
从左边数是4，即是：6 - 2 = 4

接着前面说的为什么一定需要map，map是返回一个新的数组而不改变原数组，arr.reverse()是会直接改变原数组arr的，arr.map(fn).reverse()则不会改变arr而只是改变了arr.map(fn)后返回的数组。

然而我个人觉得map的时候没必要返回一个二维数组，直接一维数组就可以了，因为后续根本用不到map后的第一个元素el[0]即它对应的索引。

如：

➜  code cat sortedLastIndexSave.js
const sortedLastIndex = (arr, n) => {
    const isDescending = arr[0] > arr[arr.length - 1];
    const index = arr
        .map(v => v)
        .reverse()
        .findIndex(el => (isDescending ? n <= el : n >= el));

    return index === -1 ? 0 : arr.length - index - 1;
};

const arr = [10, 20, 30, 30, 40];
console.log(sortedLastIndex(arr, 30));
console.log(arr);

➜  code node sortedLastIndexSave.js
3
[ 10, 20, 30, 30, 40 ]

结果一样，并且原数组arr并未改变。

sortedLastIndexBy

Returns the highest index at which value should be inserted into array in order to maintain its sort order, based on a provided iterator function.

Check if the array is sorted in descending order (loosely). Use Array.reverse() and Array.findIndex() to find the appropriate last index where the element should be inserted, based on the iterator function fn..

const sortedLastIndexBy = (arr, n, fn) => {
  const isDescending = fn(arr[0]) > fn(arr[arr.length - 1]);
  const val = fn(n);
  const index = arr
    .map((val, i) => [i, fn(val)])
    .reverse()
    .findIndex(el => (isDescending ? val <= el[1] : val >= el[1]));
  return index === -1 ? 0 : arr.length - index;
};

返回一个元素应该插入到已知排好序的数组并且不改变该数组排序方式的最大索引（从右边数的最小索引），前提是受一个指定的方法支配。

检查一个数组是否已经按降序排列（松散的），然后使用Array.reverse()和Array.findIndex()去找出指定的元素应该插在数组从右边数的合适位置的索引并返回，前提是受一个指定的方法支配。

➜  code cat sortedLastIndexBy.js
const sortedLastIndexBy = (arr, n, fn) => {
    const isDescending = fn(arr[0]) > fn(arr[arr.length - 1]);
    const val = fn(n);
    const index = arr
        .map((val, i) => [i, fn(val)])
        .reverse()
        .findIndex(el => (isDescending ? val <= el[1] : val >= el[1]));

    return index === -1 ? 0 : arr.length - index;
};

console.log(sortedLastIndexBy([{ x: 4 }, { x: 5 }], { x: 4 }, o => o.x));
console.log(sortedLastIndexBy([{ x: 40 }, { x: 30 }, { x: 30 }, { x: 20 }, { x: 10 }], { x: 30 }, o => o.x));
console.log(sortedLastIndexBy([{ x: 10 }, { x: 20 }, { x: 30 }, { x: 30 }, { x: 40 }], { x: 30 }, o => o.x));

➜  code node sortedLastIndexBy.js
1
3
4

这个跟前面的sortedLastIndex差别其实就是是否调用fn后再比较的问题，没啥可说的了。

symmetricDifference

Returns the symmetric difference between two arrays.

Create a Set from each array, then use Array.filter() on each of them to only keep values not contained in the other.

const symmetricDifference = (a, b) => {
  const sA = new Set(a),
    sB = new Set(b);
  return [...a.filter(x => !sB.has(x)), ...b.filter(x => !sA.has(x))];
};

返回两个数组中对称不相同的元素（简单说就是数组a中不存在于数组b中的所有元素加上数组b中不存在于数组a中的所有元素）。

对两个数组分别创建其集合。然后分别使用Array.filter()过滤出不存在于对方的所有元素。

➜  code cat symmetricDifference.js
const symmetricDifference = (a, b) => {
  const sA = new Set(a),
    sB = new Set(b);
  return [...a.filter(x => !sB.has(x)), ...b.filter(x => !sA.has(x))];
};

console.log(symmetricDifference([1, 2, 3], [1, 2, 4]));

➜  code node symmetricDifference.js
[ 3, 4 ]

其实前面的解释就已经很清楚了。主要看return那行：

return [...a.filter(x => !sB.has(x)), ...b.filter(x => !sA.has(x))];

a.filter(x => !sB.has(x))这里保留a数组里所有不在b数组的集合里的元素，加上…展开运算符把这些元素拼接成数组，同理，对b数组也一样。

symmetricDifferenceBy

Returns the symmetric difference between two arrays, after applying the provided function to each array element of both.

Create a Set by applying fn to each array's elements, then use Array.filter() on each of them to only keep values not contained in the other.

const symmetricDifferenceBy = (a, b, fn) => {
  const sA = new Set(a.map(v => fn(v))),
    sB = new Set(b.map(v => fn(v)));
  return [...a.filter(x => !sB.has(fn(x))), ...b.filter(x => !sA.has(fn(x)))];
};

返回两个数组中对称不相同的元素，前提是对两个数组所有元素调用指定方法后。（简单说就是数组a中不存在于数组b中的所有元素加上数组b中不存在于数组a中的所有元素，前提是调用指定方法后）。

对两个数组分别调用指定方法后创建其集合。然后分别使用Array.filter()过滤出不存在于对方的

➜  code cat symmetricDifferenceBy.js
const symmetricDifferenceBy = (a, b, fn) => {
    const sA = new Set(a.map(v => fn(v))),
        sB = new Set(b.map(v => fn(v)));
    return [...a.filter(x => !sB.has(fn(x))), ...b.filter(x => !sA.has(fn(x)))];
};

console.log(symmetricDifferenceBy([2.1, 1.2], [2.3, 3.4], Math.floor));

➜  code node symmetricDifferenceBy.js
[ 1.2, 3.4 ]

跟symmetricDifference的不同点在于多了一个fn，所以在创建集合之前，要先对数组元素map一个对所有元素运用fn的方法。再各自过滤的时候也同样使用fn对数组元素进行调用。

symmetricDifferenceWith

Returns the symmetric difference between two arrays, using a provided function as a comparator.

Use Array.filter() and Array.findIndex() to find the appropriate values.

const symmetricDifferenceWith = (arr, val, comp) => [
  ...arr.filter(a => val.findIndex(b => comp(a, b)) === -1),
  ...val.filter(a => arr.findIndex(b => comp(a, b)) === -1)
];

返回两个数组中对称不相同的元素，前提是使用一个指定的比较方法进行比较。

使用Array.filter()和Array.findIndex()来找出符合条件的所有元素。

➜  code cat symmetricDifferenceWith.js
const symmetricDifferenceWith = (arr, val, comp) => [
  ...arr.filter(a => val.findIndex(b => comp(a, b)) === -1),
  ...val.filter(a => arr.findIndex(b => comp(a, b)) === -1),
];

const res = symmetricDifferenceWith(
  [1, 1.2, 1.5, 3, 0],
  [1.9, 3, 0, 3.9],
  (a, b) => Math.round(a) === Math.round(b)
);

console.log(res);
➜  code node symmetricDifferenceWith.js
[ 1, 1.2, 3.9 ]

这个就是对数组arr，过滤出对数组arr和val所有元素调用comp方法后结果不同的所有元素。同理对数组val也一样。然后两者的结果拼接成最终的结果。