сортировка массива

[22hope22]

Как отсортировать массив по неубыванию с наименьшей затратой времени

[Abstraction]

Был какой то метод... кажется, Array.Sort(). Посмотрите - может, это оно?

[22hope22]

я как раз его и пробовала, нужно что-то побыстрее

[BDA]

Я думаю, что проблема кроется глубже, чем просто в выборе сортировки. Надеюсь, что в C# реализация Array.Sort() достаточно быстра.
Помню задачу на форуме, когда она не проходила из-за каких-то долей секунды. Обсуждаемый кусочек кода был максимально оптимизирован, но все равно не проходил. Когда руки уже опустились, ТС показал весь код, и оказалось, что в необсуждавшемся коде были логические ошибки. После их исправления программа стала в 100 раз быстрее.

[22hope22]

вот и у меня уже эти руки опускаются

[BDA]

Вы приведите условие задачи, Ваше решение, и как она прошла тесты.

[22hope22]

Исходные данные
В первой строке содержится число N — количество записей в списке преподавателя. 1 ≤ N ≤ 15000. Затем идет N строк, содержащих список преподавателя, по одной дате в строке. Записаны только года. Каждый год — целое число в пределах от 1 до 109. Даты в этом списке отсортированы по неубыванию. В следующей после списка строке содержится число M — количество записей в списке студента, 1 ≤ M ≤ 106. Затем также M строк с датами (записаны только года, каждый год — целое число в пределах от 1 до 109). Этот список не отсортирован. В списке как студента, так и преподавателя даты могут повторяться.
Результат
Вы должны вывести одно число — количество чисел во втором списке, которые также содержатся в первом.
Пример
исходные данные
2
1054
1492
4
1492
65536
1492
100
результат
2


int n1 = int.Parse(Console.ReadLine());
int[] a = new int[n1];
for (int i = 0; i < n1; i++)
{
a[i] = int.Parse(Console.ReadLine());
}

int n2 = int.Parse(Console.ReadLine());
int[] b = new int[n2];
for (int j = 0; j < n2; j++)
{
b[j] = int.Parse(Console.ReadLine());
}
int k = 0;
for (int j = 0; j < b.Length; j++)
{
for (int i = 0; i < a.Length; i++)
{
if (b[j] == a[i])
{
k++;
break;
}
}
}
Console.WriteLine(k);


завалилась на 8 тесте. Время работы программы 2.046 а надо не более 2

[22hope22]

сортировку массива совсем убрала но ничего не изменилось

[BDA]

Я же просил добавить бинпоиск
Попробуйте (не проверял, так как нет C# компилятора под рукой - не пишу на C#):

int n1 = int.Parse(Console.ReadLine());
int[] a = new int[n1];
int n3 = 1;
int tmp;
a[0] = int.Parse(Console.ReadLine());
for (int i = 1; i < n1; i++) {
  tmp = int.Parse(Console.ReadLine());
  if (tmp != a[n3 - 1]) {
    a[n3] = tmp;
    n3++;
  }
}
Array.Resize(ref a, n3);
int[] c = new int[n3];
for (int i = 0; i < n3; i++) {
  c[i] = 0;
}
int n2 = int.Parse(Console.ReadLine());
int k = 0;
for (int j = 0; j < n2; j++) {
  tmp = int.Parse(Console.ReadLine());
  tmp = Array.BinarySearch(a, tmp);
  if (tmp >= 0 && c[tmp] == 0) {
    k++;
    c[tmp] = 1;
  }
}
Console.WriteLine(k);

[BDA]

Проверил решение - оказалось, что немного его усложнил, и достаточно:

int n1 = int.Parse(Console.ReadLine());
int[] a = new int[n1];
int n3 = 1;
int tmp;
a[0] = int.Parse(Console.ReadLine());
for (int i = 1; i < n1; i++) {
  tmp = int.Parse(Console.ReadLine());
  if (tmp != a[n3 - 1]) {
    a[n3] = tmp;
    n3++;
  }
}
Array.Resize(ref a, n3);
int n2 = int.Parse(Console.ReadLine());
int k = 0;
for (int j = 0; j < n2; j++) {
  tmp = int.Parse(Console.ReadLine());
  tmp = Array.BinarySearch(a, tmp);
  if (tmp >= 0)
    k++;
}
Console.WriteLine(k);

0.625 секунд

Или совсем короткий вариант:

int n1 = int.Parse(Console.ReadLine());
int[] a = new int[n1];
for (int i = 0; i < n1; i++) {
  a[i] = int.Parse(Console.ReadLine());
}
int n2 = int.Parse(Console.ReadLine());
int k = 0;
for (int j = 0; j < n2; j++) {
  int tmp = int.Parse(Console.ReadLine());
  tmp = Array.BinarySearch(a, tmp);
  if (tmp >= 0)
    k++;
}
Console.WriteLine(k);

0.578 секунд