任务 · 算法 困难 JavaScript ·

Count inversions

/**
 * @param {number[]} nums
 * @returns {number}
 */
function count_inversions(nums)

count_inversions([2, 4, 1, 3, 5])  // -> 3
count_inversions([1, 2, 3])  // -> 0
count_inversions([3, 2, 1])  // -> 3

• 第 1 名Anthropic Claude Haiku 5.5已解决 · 通过 11/11 个测试生成耗时 2.1 秒 · 执行耗时 470 毫秒 · $0.0003

  ✓	count_inversions([2, 4, 1, 3, 5])预期 3	3 毫秒
  ✓	count_inversions([1, 2, 3])预期 0	1 毫秒
  ✓	count_inversions([3, 2, 1])预期 3	<1 毫秒

  ✓ <1 毫秒✓ 1 毫秒✓ 6 毫秒✓ 17 毫秒✓ 2 毫秒✓ 1 毫秒⏱ 343 毫秒⏱ 93 毫秒
  代码

  /**
   * @param {number[]} nums
   * @returns {number}
   */
  function count_inversions(nums) {
    const n = nums.length;
    if (n < 2) return 0;
    let a = Float64Array.from(nums);
    let b = new Float64Array(n);
    let inv = 0;
    for (let width = 1; width < n; width *= 2) {
      for (let lo = 0; lo < n; lo += 2 * width) {
        const mid = Math.min(lo + width, n);
        const hi = Math.min(lo + 2 * width, n);
        let i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
          if (a[j] < a[i]) {
            // a[j] is smaller than all remaining left elements
            inv += mid - i;
            b[k++] = a[j++];
          } else {
            b[k++] = a[i++];
          }
        }
        while (i < mid) b[k++] = a[i++];
        while (j < hi) b[k++] = a[j++];
      }
      const t = a; a = b; b = t;
    }
    return inv;
  }

• 第 1 名MoonshotAI Kimi K2.7 Code已解决 · 通过 11/11 个测试生成耗时 14 秒 · 执行耗时 572 毫秒 · $0.0040

  ✓	count_inversions([2, 4, 1, 3, 5])预期 3	5 毫秒
  ✓	count_inversions([1, 2, 3])预期 0	1 毫秒
  ✓	count_inversions([3, 2, 1])预期 3	3 毫秒

  ✓ 2 毫秒✓ <1 毫秒✓ 3 毫秒✓ 2 毫秒✓ 1 毫秒✓ 2 毫秒⏱ 337 毫秒⏱ 217 毫秒
  代码

  /**
   * @param {number[]} nums
   * @returns {number}
   */
  function count_inversions(nums) {
      const n = nums.length;
      const arr = nums.slice();
      const temp = new Array(n);
  
      function sort(left, right) {
          if (right - left <= 1) return 0;
          const mid = (left + right) >>> 1;
          let count = sort(left, mid) + sort(mid, right);
  
          let i = left;
          let j = mid;
          let k = left;
  
          while (i < mid && j < right) {
              if (arr[i] <= arr[j]) {
                  temp[k++] = arr[i++];
              } else {
                  temp[k++] = arr[j++];
                  count += mid - i;
              }
          }
          while (i < mid) temp[k++] = arr[i++];
          while (j < right) temp[k++] = arr[j++];
  
          for (let p = left; p < right; p++) {
              arr[p] = temp[p];
          }
  
          return count;
      }
  
      return sort(0, n);
  }

• 第 1 名SpaceXAI Grok Build 0.1已解决 · 通过 11/11 个测试生成耗时 18 秒 · 执行耗时 714 毫秒 · $0.0056

  ✓	count_inversions([2, 4, 1, 3, 5])预期 3	3 毫秒
  ✓	count_inversions([1, 2, 3])预期 0	<1 毫秒
  ✓	count_inversions([3, 2, 1])预期 3	3 毫秒

  ✓ 1 毫秒✓ <1 毫秒✓ 2 毫秒✓ 1 毫秒✓ <1 毫秒✓ 2 毫秒⏱ 382 毫秒⏱ 317 毫秒
  代码

  function count_inversions(nums) {
      if (!nums || nums.length <= 1) return 0;
      const arr = nums.slice();
      return mergeSort(arr, 0, arr.length - 1);
      function mergeSort(arr, left, right) {
          if (left >= right) return 0;
          const mid = Math.floor((left + right) / 2);
          let count = mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right);
          count += merge(arr, left, mid, right);
          return count;
      }
      function merge(arr, left, mid, right) {
          const temp = new Array(right - left + 1);
          let i = left, j = mid + 1, k = 0;
          let count = 0;
          while (i <= mid && j <= right) {
              if (arr[i] <= arr[j]) {
                  temp[k++] = arr[i++];
              } else {
                  temp[k++] = arr[j++];
                  count += (mid - i + 1);
              }
          }
          while (i <= mid) {
              temp[k++] = arr[i++];
          }
          while (j <= right) {
              temp[k++] = arr[j++];
          }
          for (let p = 0; p < k; p++) {
              arr[left + p] = temp[p];
          }
          return count;
      }
  }

• 第 1 名Z.ai GLM 5.3已解决 · 通过 11/11 个测试生成耗时 1.4 秒 · 执行耗时 863 毫秒 · $0.0009

  ✓	count_inversions([2, 4, 1, 3, 5])预期 3	3 毫秒
  ✓	count_inversions([1, 2, 3])预期 0	<1 毫秒
  ✓	count_inversions([3, 2, 1])预期 3	<1 毫秒

  ✓ 2 毫秒✓ <1 毫秒✓ 2 毫秒✓ 1 毫秒✓ 2 毫秒✓ <1 毫秒⏱ 552 毫秒⏱ 299 毫秒
  代码

  function count_inversions(nums) {
    const n = nums.length;
    if (n < 2) return 0;
    const sorted = Array.from(nums).sort((a, b) => a - b);
    const rank = new Map();
    let r = 0;
    for (const v of sorted) if (!rank.has(v)) rank.set(v, ++r);
    const tree = new Uint32Array(r + 1);
    const add = (i) => { for (; i <= r; i += i & -i) tree[i]++; };
    const query = (i) => { let s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; };
    let inv = 0;
    for (let i = n - 1; i >= 0; i--) {
      inv += query(rank.get(nums[i]) - 1);
      add(rank.get(nums[i]));
    }
    return inv;
  }

Token 成本: $0.01 · 轮次运行与评分规则 →