Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
1 / 0 / 1
Регистрация: 08.09.2018
Сообщений: 46
1

Число, встречающееся во всех строках двумерного массива

14.10.2018, 15:44. Показов 925. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем добрый день.
Никак не догоню, как решать.
Условие задачи: дан двумерный массив n*m (целочисленный). все строки имеют возрастающую последовательность. Существует как минимум одно число, которое присутствует в каждой строке массива. Вывести его.

Как можно сделать это без использования библиотек (т.е. ручками) за минимальное число итераций?
На уровне псевдокода можно или вообще словами, поскольку не знаю как подойти к решению этой ситуации.

И возможно ли вообще не проходиться по всему массиву?

Спасибо.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.10.2018, 15:44
Ответы с готовыми решениями:

Матрица. Найти число, встречающееся во всех строках
Дана матрица P размерности n×m. Каждая строка массива упорядочена по возрастанию. Найти число,...

Составить программу нахождения числа, встречающегося во всех строках двумерного массива
Составить программу нахождения числа, встречающегося во всех строках двумерного массива A(N,M),...

Составьте программу нахождения числа, встречающегося во всех строках двумерного массива B(Q, P)
Составьте программу нахождения числа, встречающегося во всех строках двумерного массива А(N, N)....

Составьте программу нахождения числа, встречающегося во всех строках двумерного массива
Составьте программу нахождения числа, встречающегося во всех строках двумерного массива А(N7,N),...

1
1 / 0 / 1
Регистрация: 08.09.2018
Сообщений: 46
20.10.2018, 09:06  [ТС] 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main()
{
    int n, m;
    cin >> n >> m;
 
    int **a = new int*[n]; 
    for (int count = 0; count < n; count++)
        a[count] = new int[m];
 
    int counter = 1, memory = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> a[i][j];
 
    for (int j = 0; j < m; j++)
    {
        for (int i = 1; i < n; i++)
        {
            int l = 0;
            int r = m - 1;
            int mid = 0;
            while (l < r)
            {   mid = (l + r) / 2;
                if (a[i][mid] == a[0][j])
                {
                    l = r = mid;
                    memory = a[0][j];
                }
                else if (a[i][mid] < a[0][j]) l = mid + 1;
                
                else r = mid;
            }
            if (a[i][r] == a[0][j]) counter++;
            else i = n;
        }
        if (counter == n)
        {
            memory = a[0][j];
            j = m;
        }
    }
    cout << memory << endl;
}
сделал бинарным поиском. получается C*n*m*log(2)m;
подскажите, пожалуйста, чем можно уменьшить до <C*m*n?
0
20.10.2018, 09:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.10.2018, 09:06
Помогаю со студенческими работами здесь

Вставить после всех строк (двумерного массива), в которых есть заданное число А, последнюю строку
Вставить после всех строк (двумерного массива), в которых есть заданное число А, последнюю строку....

Наибольшие элементы в строках двумерного массива
Доброго времени суток! Есть задача Набросал такой код: var i, j, n, mChoise, nChoise:...

найти минимальную сумму элементов в строках двумерного массива
найти минимальную сумму элементов в строках двумерного массива Помогите пожалуйста

Найти минимальную сумму элементов в строках двумерного массива
найти минимальную сумму элементов в строках двумерного массива


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru