Saturday, March 21, 2009

Algorithms: Distinct an array

Внимание 
Код приведенный в этой заметке написан на C#.

Задача: дан отсортированный массив целых чисел. Необходимо удалить в массиве все повторения и получить массив, в котором сначала идут неповторяющиеся числа, а остальные элементы массива должны быть заполнены нулями.

Рассмотрим простой пример. Возмем массив в котором есть 2 повторяющихся числа: {1, 2, 3, 3, 4, 5, 5, 5, 6}. В данном массиве числа 3 и 5 повторяются несколько раз. В результате необходимо вернуть массив: {1, 2, 3, 4, 5, 6, 0, 0, 0}.

Приведу возможное решение задачи (коментарии по коду):

    1 /// <summary>

    2 /// Task: distinct an array.

    3 /// Requirements: array of integers, sorted in ascending order.

    4 /// Use the same array object and return its distinct value.

    5 /// Distinct values should come first, and the remaining

    6 /// elements must be filled with zeros.

    7 /// For instance:

    8 /// {1, 2, 2, 3, 4, 4, 5 } => {1, 2, 3, 4, 5, 0, 0}.

    9 ///

   10 /// Complexity: O(n).

   11 /// </summary>

   12 /// <param name="input">Target array.</param>

   13 /// <returns>Distinct array.</returns>

   14 public static int[] DistinctArray(int[] input)

   15 {

   16     // First of all, we need to check the input array.

   17     if (input == null || input.Length == 0)

   18     {

   19         throw new ArgumentNullException("input");

   20     }

   21 

   22     int position = 0;

   23     for (int index = 1; index < input.Length; index++)

   24     {

   25         if (input[index] != input[position])

   26         {

   27             input[++position] = input[index];

   28         }

   29     }

   30 

   31     for (int index = position + 1; index < input.Length; index++)

   32     {

   33         input[index] = 0;

   34     }

   35 

   36     return input;

   37 }

Такое решение имеет сложность O(n).

И в заключение - пример использования:

    1 int[] inputArray = { 1, 2, 3, 3, 4, 5, 5, 5, 6 };

    2 inputArray.PrintArray();

    3 var outputArray = ArrayUtilities.DistinctArray(inputArray);

    4 outputArray.PrintArray();

Запускаем, и....

image

PS:

наверное у кого-то может возникнуть вопрос: "как так получилось - inputArray.PrintArray()?" - так вот это всего лишь вспомогательный extension-метод. Приведу его кот потому что он может нам (мне и тебе ув. %username%) еще пригодится.

    1 /// <summary>

    2 /// Prints an array.

    3 /// </summary>

    4 /// <typeparam name="T">Array type.</typeparam>

    5 /// <param name="input">Input array instance.</param>

    6 public static void PrintArray<T>(this T[] input)

    7 {

    8     if (input == null)

    9     {

   10         Console.WriteLine("Input array is null.");

   11         return;

   12     }

   13 

   14     Console.Write(typeof(T).Name + "[" + input.Length + "] = {");

   15     for (var index = 0; index < input.Length; index++)

   16     {

   17         Console.Write(input[index]);

   18         if (index < input.Length - 1)

   19         {

   20             Console.Write(", ");

   21         }

   22     }

   23     Console.WriteLine("}");

   24 }

В следующий раз я раскажу как перевести число в строку :) (без использования int.ToString()).

Happy coding...

No comments :

Post a Comment