Количество инверсий в массиве - C#
Формулировка задачи:
Добрый день. Необходимо написать программу, которая выведет количество инверсий в массиве.
Помогите разобраться и найти где ошибка.
Дано:
Я написал код, который выдает 2232, что не является правильным ответом. И не могу понять, где ошибка:
public class SortProblem { public static void Main() { Sort(); } public static void Sort() { var a = new [] { 11,86,232,28,8,145,588,1,307,179,77,792,693,678,481,888,574,695,624,866,467,434,907,259,130,37,25,373,214,268,108,672,371,866,863,279,22,233,336,830,374,439,144,234,360,617,244,5,566,847,476,493,56,618,202,576,179,972,898,970,119,214,786,38,71,404,420,827,814,201,865,341,358,794,492,27,290,672,899,512,792,20,807,367,792,615,616,753,663,287,99,49,334,366,711,160,652,105,162,955 };
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; public class SortProblem { static double inversionsCount; public static void Main() { var arr = new[] { 11,86,232,28,8,145,588,1,307,179,77,792,693,678,481,888,574,695,624,866,467,434,907,259,130,37,25,373,214,268,108,672,371,866,863,279,22,233,336,830,374,439,144,234,360,617,244,5,566,847,476,493,56,618,202,576,179,972,898,970,119,214,786,38,71,404,420,827,814,201,865,341,358,794,492,27,290,672,899,512,792,20,807,367,792,615,616,753,663,287,99,49,334,366,711,160,652,105,162,955 }; inversionsCount = 0; arr = Sort(arr); Console.Write($"{inversionsCount}"); Console.ReadLine(); } static int[] Sort(int[] buff) { if (buff.Length > 1) //Если длинна массива больше 1 { int[] left = new int[buff.Length / 2]; // массив left равен длинна вставленного массива разделить на 2 int[] right = new int[buff.Length - left.Length]; // массив right равен длинна вставленного массива минус массив left for (int i = 0; i < left.Length; i++) // равно 0 , меньше длинны массива left, добавялем 1 { left[i] = buff[i]; // результат left[i] = buff[i] } for (int i = 0; i < right.Length; i++) // массив right { right[i] = buff[left.Length + i]; } /*Сортируем массивы*/ if (left.Length > 1) left = Sort(left); if (right.Length > 1) right = Sort(right); buff = MergeSort(left, right); } return buff; } static int[] MergeSort(int[] left, int[] right) { int[] buff = new int[left.Length + right.Length]; int i = 0; //соединенный массив int l = 0; //левый массив int r = 0; //правый массив for (; i < buff.Length; i++) { if (r >= right.Length) { buff[i] = left[l]; l++; } else if (l < left.Length && left[l] < right[r]) { buff[i] = left[l]; l++; } else { buff[i] = right[r]; r++; if (l < left.Length) inversionsCount += left.Length - l; } } return buff; } }
Решение задачи: «Количество инверсий в массиве»
textual
Листинг программы
else if (l < left.Length && left[l] <= right[r])
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д