Telle inversjoner i et array med TypeScript

Jeg har dunket hodet mitt mot denne feilen i et par timer nå og ser ut til å ikke finne hvor feilen er.

Jeg prøver å telle inversjonene i et gitt array, og alle testene mine passer bortsett fra når jeg bruker dette arrayet som input [6, 1, 2, 5, 4, 3].

Logikken er som følger; gitt array A[1... n], for hver i < j, finn alle inversjonsparet slik at A[i] > A[j]

Tallet jeg får for dette arrayet er 14 inversjoner, og det riktige svaret er 8.

Koden så langt er dette

function mergeCount(left: number[], right: number[]): number {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      leftCounter += 1;
    } else {
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return count;
}

function countInversions(input: number[]): number {
  if (input.length < 2) return 0;

  const middle = Math.floor(input.length / 2);

  const left = input.slice(0, middle);
  const right = input.slice(middle);

  return countInversions(left) + countInversions(right) + mergeCount(left, right);
}

Noe ide om hva jeg mangler eller hva som er galt med koden min?

REDIGER :

Så problemet var at jeg ikke sorterte arrayene når jeg delte dem opp, jeg oppdaterte bare telleren. Den fungerende løsningen jeg kom opp med er som følger

function mergeCount(left: number[], right: number[]): { output: number[]; count: number } {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;
  const output: number[] = [];

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      output.push(left[leftCounter]);
      leftCounter += 1;
    } else {
      output.push(right[rightCounter]);
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return {
    output: output.concat(left.slice(leftCounter)).concat(right.slice(rightCounter)),
    count,
  };
}

function countInversions(input: number[]): { output: number[]; count: number } {
  if (input.length < 2) return { output: input, count: 0 };

  const middle = Math.floor(input.length / 2);

  const { output: left, count: a } = countInversions(input.slice(0, middle));
  const { output: right, count: b } = countInversions(input.slice(middle));
  const { output, count: c } = mergeCount(left, right);

  return { output, count: a + b + c };
}

Svar #1

Python-koden du lenket til sorterer også arrayet - det gjør ikke du. Dette kan føre til feil svar, fordi inversjonstellingsalgoritmen basert på mergesort krever at du også sorterer arrayet samtidig (ellers vil ikke snarveien den bruker være gyldig).

Enkelt slå sammen left og right i din mergeCount-funksjon, returner det også, og det bør fungere.

Den uthevede Pythonen nedenfor er det som mangler i koden din:

 while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]) # this
            i += 1
        else:
            result.append(right[j]) # and this
            count += left_len - i
            j += 1

For å gi mer bakgrunn på ideen om inversjonstelling med mergesort:

I mergesort har vi to sorterte halvdeler H1 og H2: H1 er sortert, H2 er sortert. Vi har en merge-funksjon som slår disse to sammen, effektivt, til ett stort sortert array.

Nå, det er (vel, bør være) gjort i OPs while-løkke. Merk at, hvis, man bruker hans notasjon:

left[leftCounter] > right[rightCounter]

(hans ellers-betingelse), så fordi left er sortert, vil alle elementene etter leftCounter også være større enn right[rightCounter], så vi har left.length - leftCounter inversjoner - noe som lar oss telle mer enn 1 om gangen.

Selvfølgelig gjelder dette bare hvis du lar mergesort gjøre jobben sin og faktisk sortere arrayet.

Svar #2

Den nåværende implementeringen ser ganske komplisert ut. Jeg tror den kunne vært mye enklere (og mer nøyaktig).

Iterer over alle elementer i en ytre løkke. La oss kalle indeksen i. Inne i den indre løkken, iterer over alle elementer som er større enn i og sammenlign dem med elementet i den ytre løkken.

function countInversions(input: number[]): number {
    let count = 0;
    for (let i = 0; i < input.length; i++) {
        for (const num of input.slice(i + 1)) {
            if (input[i] > num) {
                count++;
            }
        }
    }
    return count;
}

Relaterte artikler