المهمة · خوارزميات صعب 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 مللي ثانية · $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;
  }

• المركز 1MoonshotAI 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);
  }

• المركز 1SpaceXAI 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;
      }
  }

• المركز 1Z.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;
  }

تكلفة الرموز: $0.01 · كيف تُدار الجولات وتُحتسب النقاط ←