Ищем в матрице количество повторяющихся элементов

Задача определения в двумерном массиве количества элементов, для которых есть элементы с такими же значениями - не столь уж тривиальная. Нам понадобится, во-первых, придумать, как организовать сравнение каждого элемента матрицы с каждым. Для вектора (одномерного массива) a из n элементов было бы элементарно - организовать двойной цикл вида

int i,j;
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++) {
 //Сравниваем a[i] и a[j]
}

Но ведь к матрице тоже можно обращаться как к вектору, если организовать "сквозные" счётчики элементов i и j, меняющиеся в пределах [0,n*m-2], [i+1,n*m-1] соответственно, и затем брать в двойном цикле элементы матрицы a[i/m][i%m] и a[j/m][j%m].

Кроме того, нам придётся учесть, что подсчитать количество выполнений равенства a[i/m][i%m]==a[j/m][j%m] недостаточно - некоторые элементы могут быть подсчитаны неоднократно. Поэтому перед обработкой очередного элемента a[i/m][i%m] нужно проверить, не было ли перед ним в матрице таких же значений. Если да, элемент уже был обработан (флаг found в программе).

Ну и количество выполнений равенства не есть искомое количество "элементов с повторами" - если в матрице 3 числа-двойки, с ними будет сделано только 2 сравнения (флаг found2 в программе корректирует проблему).

//Ищем в матрице количество повторяющихся элементов
#include <stdio.h>
int main () {
const int n=3,m=4;
int a[n][m] = {
 {1,2,3,3},
 {5,5,7,8},
 {9,9,11,9}
};
//или ввод матрицы a[n][m]
int i,j,l,i1,i2,j1,j2,k,kmax=0,imax,all=0,found,found2;
for (i=0; i<n*m-1; i++) {
 found = 1; //надо ли искать "вниз" от текущего элемента
 i1 = i/m; j1 = i%m;
 for (l=0; l<i; l++) { //если раньше был такой элемент - искать с него не надо
  i2 = l/m; j2 = l%m;
  if (a[i1][j1]==a[i2][j2]) { found = 0; break; }
 }
 if (found) {
  found2 = 0; //найдено ли "вниз" от текущего элемента
  for (j=i+1; j<n*m; j++) { //ищем после элемента такие же по значению
   i2 = j/m; j2 = j%m;
   if (a[i1][j1]==a[i2][j2]) {
    all++; found2 = 1;
   }
  }
  if (found2) all++;
 }
 //ищем макс.количество повторов в строке kmax
 k = 0;
 for (j=0; j<m; j++) if (a[i1][j]==a[i1][j1]) k++;
 if (k>kmax) { kmax = k; imax = i1; }
}
if (all>0) {
 printf ("\nВсего элементов с повторами значений: %d\
  \nСтрока с наибольшим числом одинаковых: ",all);
 for (j=0; j<m; j++) printf ("%d ",a[imax][j]);
}
else printf ("\nНет повторов!");
getchar();
return 0;
}

Наверняка возможен алгоритм получше, просто нужно было быстрое "лобовое" решение.

Дополнительно в примере ищется номер первой из строк, содержащих наибольшее количество одинаковых элементов (переменная imax).

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

//Выводим не-повторяющиеся элементы матрицы
#include <cstdio>
int main() {
 const int n = 3, m = 4;
 int a[n][m] = {
  { 1,2,3,3 },
  { 5,5,7,8 },
  { 9,9,11,9 }
 }; //или ввод матрицы a[n][m]
 int i, j, l, i1, i2, j1, j2, found, found2;
 for (i = 0; i < n * m - 1; i++) {
  found = 1; //надо ли искать "вниз" от текущего элемента
  i1 = i / m; j1 = i % m;
  for (l = 0; l < i; l++) { //если раньше был такой элемент - искать с него не надо
   i2 = l / m; j2 = l%m;
   if (a[i1][j1] == a[i2][j2]) { found = 0; break; }
  }
  if (found) {
   found2 = 0; //найдено ли "вниз" от текущего элемента
   for (j = i + 1; j < n*m; j++) { //ищем после элемента такие же по значению
    i2 = j / m; j2 = j%m;
    if (a[i1][j1] == a[i2][j2]) {
     found2 = 1; break;
    }
   }
   if (!found2) {
    printf("%d ", a[i1][j1]);
   }
  }
 }
 
 getchar();
 return 0;
}

Если работать с одномерным массивом, можно решить и за время O(n), но ценой "порчи" элементов массива или использования копии массива в памяти.

07.10.2014, 15:42 [20627 просмотров]