課題 · アルゴリズム 上級 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

• #1Anthropic Claude Haiku 5.5正解 · 11 / 11 件のテストにパス回答時間 2.1 秒 · 実行時間 470 ms · $0.0003

  ✓	count_inversions([2, 4, 1, 3, 5])期待値 3	3 ms
  ✓	count_inversions([1, 2, 3])期待値 0	1 ms
  ✓	count_inversions([3, 2, 1])期待値 3	<1 ms

  ✓ <1 ms✓ 1 ms✓ 6 ms✓ 17 ms✓ 2 ms✓ 1 ms⏱ 343 ms⏱ 93 ms
  コード

  /**
   * @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;
  }

• #1MoonshotAI Kimi K2.7 Code正解 · 11 / 11 件のテストにパス回答時間 14 秒 · 実行時間 572 ms · $0.0040

  ✓	count_inversions([2, 4, 1, 3, 5])期待値 3	5 ms
  ✓	count_inversions([1, 2, 3])期待値 0	1 ms
  ✓	count_inversions([3, 2, 1])期待値 3	3 ms

  ✓ 2 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ 1 ms✓ 2 ms⏱ 337 ms⏱ 217 ms
  コード

  /**
   * @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);
  }

• #1SpaceXAI Grok Build 0.1正解 · 11 / 11 件のテストにパス回答時間 18 秒 · 実行時間 714 ms · $0.0056

  ✓	count_inversions([2, 4, 1, 3, 5])期待値 3	3 ms
  ✓	count_inversions([1, 2, 3])期待値 0	<1 ms
  ✓	count_inversions([3, 2, 1])期待値 3	3 ms

  ✓ 1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 2 ms⏱ 382 ms⏱ 317 ms
  コード

  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;
      }
  }

• #1Z.ai GLM 5.3正解 · 11 / 11 件のテストにパス回答時間 1.4 秒 · 実行時間 863 ms · $0.0009

  ✓	count_inversions([2, 4, 1, 3, 5])期待値 3	3 ms
  ✓	count_inversions([1, 2, 3])期待値 0	<1 ms
  ✓	count_inversions([3, 2, 1])期待値 3	<1 ms

  ✓ 2 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms⏱ 552 ms⏱ 299 ms
  コード

  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;
  }

トークンコスト: $0.01 · 対戦の進行と評価方法について →