Условие задачи:
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).
Реализация:
private static string separator = ";";
static void Main(string[] args)
{
int[] result = GetIntArray(InputArray());
PrintArray(result);
Console.WriteLine(ff(result));
Console.ReadLine();
}
private static string InputArray()
{
Console.WriteLine("Введите массив, содержащий только целые числа.");
Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
Console.WriteLine("Введите массив: ");
return Console.In.ReadLine();
}
private static int[] GetIntArray(string insert)
{
string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
string[] bufResult = Regex.Split(insert, pattern);
int[] result = new int[bufResult.Length];
for (int i = 0; i < bufResult.Length; i++)
{
result[i] = Int32.Parse(bufResult[i]);
}
return result;
}
private static void PrintArray(int[] array)
{
foreach(int i in array)
{
Console.WriteLine(i);
}
}
private static int ff(int[] array)
{
int m = 1;
int buf = 0;
// общее количество сравнений (n-1)^2, где n - длина массиваfor (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
{
// количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)for (int j = 1; j < array.Length; j++)
{
if (array[0] == array[j])
{
buf = array[0];
goto result;
}
}
Swap(array, m);
m++;
}
result:
return buf;
}
private static void Swap(int[] array, int index)
{
int temp = array[index];
array[index] = array[0];
array[0] = temp;
}
Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
for (int j = 1; j < array.Length - 1; j++)
при этом работа цикла
for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Xobotik, Вы писали:
X>>Найти это число за время O(N).
X>> // общее количество сравнений (n-1)^2, где n — длина массива
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Можете сказать хоть куда копать? Голова забита только этим методом.
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Здравствуйте, Xobotik, Вы писали:
X>>>Найти это число за время O(N).
X>>> // общее количество сравнений (n-1)^2, где n — длина массива
X>А разве O((n-1)^2) ~ O(n)?
Здравствуйте, Xobotik, Вы писали:
X>Есть ли какие-либо другие пути решения задачи?
Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Можете сказать хоть куда копать? Голова забита только этим методом.
S>Нужно копать в сторону удовлетворения требования O(N)
S>Если скажу больше, то будет неинтересно
private static int fff(int[] array)
{
int buf = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] == array[i+1])
{
continue;
}
else
{
buf = array[i];
return buf;
}
}
return buf;
}
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
X>Реализация: X>
X>private static string separator = ";";
X> static void Main(string[] args)
X> {
X> int[] result = GetIntArray(InputArray());
X> PrintArray(result);
X> Console.WriteLine(ff(result));
X> Console.ReadLine();
X> }
X> private static string InputArray()
X> {
X> Console.WriteLine("Введите массив, содержащий только целые числа.");
X> Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
X> Console.WriteLine("Введите массив: ");
X> return Console.In.ReadLine();
X> }
X> private static int[] GetIntArray(string insert)
X> {
X> string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
X> string[] bufResult = Regex.Split(insert, pattern);
X> int[] result = new int[bufResult.Length];
X> for (int i = 0; i < bufResult.Length; i++)
X> {
X> result[i] = Int32.Parse(bufResult[i]);
X> }
X> return result;
X> }
X> private static void PrintArray(int[] array)
X> {
X> foreach(int i in array)
X> {
X> Console.WriteLine(i);
X> }
X> }
X> private static int ff(int[] array)
X> {
X> int m = 1;
X> int buf = 0;
X> // общее количество сравнений (n-1)^2, где n - длина массива
X> for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X> {
X> // количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)
X> for (int j = 1; j < array.Length; j++)
X> {
X> if (array[0] == array[j])
X> {
X> buf = array[0];
X> goto result;
X> }
X> }
X> Swap(array, m);
X> m++;
X> }
X> result:
X> return buf;
X> }
X> private static void Swap(int[] array, int index)
X> {
X> int temp = array[index];
X> array[index] = array[0];
X> array[0] = temp;
X> }
X>
X>Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
X>
X>for (int j = 1; j < array.Length - 1; j++)
X>
X>при этом работа цикла
X>
X>for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X>
X>не прерывается
X>Заранее спасибо!
private static int fff(int[] array)
{
int buf = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] == array[i+1])
{
continue;
}
else
{
buf = array[i];
return buf;
}
}
return buf;
}
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, Xobotik, Вы писали:
X>>Есть ли какие-либо другие пути решения задачи? E>Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
X> private static int fff(int[] array)
X> {
X> int buf = 0;
X> for (int i = 0; i < array.Length; i++)
X> {
X> if (array[i] == array[i+1])
X> {
X> continue;
X> }
X> else
X> {
X> buf = array[i];
X> return buf;
X> }
X> }
X> return buf;
X> }
X>
X>Удовлетворяет условию O(N)?
Удовлетворяет O(N) но не решает задачу. Вернет первый элемент массива, который не дублируется следующим элементом массива. До конца массива не дойдет, вылетит по IndexOutOfRangeException.
Здравствуйте, elmal, Вы писали:
E>Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
Полагаю, что автор задачи вряд ли рассчитывал увидеть в решении задачи по теме массивов HashSet.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>
X>> private static int fff(int[] array)
X>> {
X>> int buf = 0;
X>> for (int i = 0; i < array.Length; i++)
X>> {
X>> if (array[i] == array[i+1])
X>> {
X>> continue;
X>> }
X>> else
X>> {
X>> buf = array[i];
X>> return buf;
X>> }
X>> }
X>> return buf;
X>> }
X>>
X>>Удовлетворяет условию O(N)?
S>Удовлетворяет O(N) но не решает задачу. Вернет первый элемент массива, который не дублируется следующим элементом массива. До конца массива не дойдет, вылетит по IndexOutOfRangeException.
Ну то есть получается надо решить задачу используя только один цикл.
Здравствуйте, Xobotik, Вы писали:
X>Ну то есть получается надо решить задачу используя только один цикл.
Не совсем верно. O(N) допускает кол-во операций, пропорциональное N. Т.е. это может быть один цикл по N, два цикла по N, три и более, но главное чтобы число циклов не зависело от N и чтобы циклы не были вложенными.
На самом деле вложенные тоже можно, но число итераций вложенных циклов не должно зависеть от N.
примеры, удовлетворяющие оценке O(N):
for(int i = 0; i < N-1; i++)
{
...
}
for(int k = N-1; k >=0; k--)
{
...
}
for(int i = 0; i < N-1; i++)
{
for(int k = 0; k < 100; k++)
{
...
}
}
Это об оценке кол-ва операций O(N).
А возвращаясь к задаче — да, эта задача решается с помощью одного цикла.
Здравствуйте, samius, Вы писали:
S>Полагаю, что автор задачи вряд ли рассчитывал увидеть в решении задачи по теме массивов HashSet.
Лично я бы, если бы дал такую задачу, именно такое решение бы и ожидал увидеть. Так как такие задачи довольно часты на практике, и по крайней мере я их всегда через HashSet делаю. Конечно есть решение и без HashSet, именно оно и ожидается скорее всего (где то я в этюдах решение видел, насколько я понимаю, основная идея тогда — построить такую контрольную сумму, чтобы можно было вычислить дубликат), но сходу я б ее не решил быстро, как и не ожидал бы такого решения от кандидата. Да и не очень будет это решение, при всей своей мегаоптимальности и красивости универсальным, ни разу у меня не было случая, когда постановка задачи была именно такая (именно 2 раза встречается, и именно от 1 до М).
PS Пока писал — вспомнил решение . А топикстартуру — пусть гуглит, где то здесь проскакивало, наводку я дал
