Задача · алгоритмы сложная 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;
  }

Стоимость токенов: $0.01 · Как проходят и оцениваются раунды →