取两个重复数组的交集

const set_intersection = (set1, set2) => {
  if (set1.size > set2.size) {
    return set_intersection(set2, set1);
  }
  const intersection = new Set();
  for (const num of set1) {
    if (set2.has(num)) {
      intersection.add(num);
    }
  }
  return [...intersection];
};

var intersection = function (nums1, nums2) {
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);
  return set_intersection(set1, set2);
};

new set 不能用 for 循环 取不到具体数值

取它们的并集

let aSet = new Set(a);
let bSet = new Set(b);
let union = Array.from(new Set(a.concat(b))); // [1,2,3,4,5]

编写一个函数计算多个数组的交集

var intersection = function (...args) {
  if (args.length === 0) {
    return [];
  }
  if (args.length === 1) {
    return args[0];
  }
  return [
    ...new Set(
      args.reduce((result, arg) => {
        return result.filter((item) => arg.includes(item));
      })
    ),
  ];
};
const findKthLargest = (nums, k) => {
  const n = nums.length;

  const quick = (l, r) => {
    if (l > r) return;
    let random = Math.floor(Math.random() * (r - l + 1)) + l; // 随机选取一个index
    swap(nums, random, r); // 将它和位置r的元素交换,让 nums[r] 作为 pivot 元素
    /**
     * 我们选定一个 pivot 元素,根据它进行 partition
     * partition 找出一个位置:它左边的元素都比pivot小,右边的元素都比pivot大
     * 左边和右边的元素的是未排序的,但 pivotIndex 是确定下来的
    */
    let pivotIndex = partition(nums, l, r);
    /**
     * 我们希望这个 pivotIndex 正好是 n-k
     * 如果 n - k 小于 pivotIndex,则在 pivotIndex 的左边继续找
     * 如果 n - k 大于 pivotIndex,则在 pivotIndex 的右边继续找
     */
    if (n - k < pivotIndex) {
      quick(l, pivotIndex - 1);
    } else {
      quick(pivotIndex + 1, r);
    }
    /**
     * n - k == pivotIndex ,此时 nums 数组被 n-k 分成两部分
     * 左边元素比 nums[n-k] 小,右边比 nums[n-k] 大,因此 nums[n-k] 就是第K大的元素
     */
  };

  quick(0, n - 1); // 让n-k位置的左边都比 nums[n-k] 小,右边都比 nums[n-k] 大
  return nums[n - k];
};

function partition(nums, left, right) {
  let pivot = nums[right];             // 最右边的元素作为 pivot 元素
  let pivotIndex = left;               // pivotIndex 初始为 left
  for (let i = left; i < right; i++) { // 逐个考察元素,和 pivot 比较
    if (nums[i] < pivot) {             // 如果当前元素比 pivot 小
      swap(nums, i, pivotIndex);       // 将它交换到 pivotIndex 的位置
      pivotIndex++;
    }
  }                                    // 循环结束时,pivotIndex左边都是比pivot小的
  swap(nums, right, pivotIndex);       // pivotIndex和right交换,更新pivot元素
  return pivotIndex;                   // 返回 pivotIndex 下标
}

function swap(nums, p, q) {
  const temp = nums[p];
  nums[p] = nums[q];
  nums[q] = temp;
}

Array.slice() 该方法并不会修改数组,而是返回一个子数组。如果想删除数组中的一段元素,应该使用方法 Array.splice().

/**

  • 数组扁平化、去重、排序 */ const list = [1, [2, 3, 8], [3, 6, 4], [5, [6, 7, [8, 1, 2]]]];

/====== 扁平化 ======/

function flat(arr) {
  return arr.reduce((acc, cur) => {
    acc = acc.concat(Array.isArray(cur) ? flat(cur) : cur);
    return acc;
  }, []);
}

/====== 数组去重 ======/

function unique(arr) {
  return arr.reduce((acc, cur) => {
    if (!acc.includes(cur)) acc.push(cur);
    return acc;
  }, []);
}

/====== 排序 ======/ // 冒泡排序

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

const flatArr = flat(list); console.log('flatArr: ', flatArr); // [1, 2, 3, 8, 3, 6, 4, 5, 6, 7, 8, 1, 2]

const uniArr = unique(flatArr); console.log('uniArr: ', uniArr); // [1, 2, 3, 8, 6, 4, 5, 7]

const sortArr = bubbleSort(uniArr); // [1, 2, 3, 4, 5, 6, 7, 8] console.log('sortArr: ', sortArr);

最后更新于

这有帮助吗?