Линейный поиск в двумерном массиве.
0 1 0 1 1 0
1 0 1 1 0 0
0 0 0 1 0 1
0 0 0 0 0 0
1 0 1 1 0 0
0 1 0 1 1 1
Вход: определим что дыра k это когда в строке ее все нули ,а в столбце все 1 кроме самого k который равен 0. Выход: существует ли такой k и если да вернуть его значение если нет вернуть -1. Код должен пройти со сложностью O(n). Метод: public static int isSink(int [][] mat)
я написала такой код,но мне сказали что он неверный:
Код:
public static int isSink(int[][] mat) {
int n = mat[0].length;
boolean[] check = new boolean[n];
for (int i = 0; i < n; i++)
check[i] = true;
for (int i = 0; i < n; i++)
if (check[i]) {
for (int j = 0; j < n; j++) {
if (i != j)
check[j] = false;
else {
check[i] = false;
break;
}
if (i == j)
continue;
if (mat[j][i] == 1)
check[j] = false;
else {
check[i] = false;
break;
}
}
if (check[i])
return i;
}
return -1;
}
int n = mat[0].length;
boolean[] check = new boolean[n];
for (int i = 0; i < n; i++)
check[i] = true;
for (int i = 0; i < n; i++)
if (check[i]) {
for (int j = 0; j < n; j++) {
if (i != j)
check[j] = false;
else {
check[i] = false;
break;
}
if (i == j)
continue;
if (mat[j][i] == 1)
check[j] = false;
else {
check[i] = false;
break;
}
}
if (check[i])
return i;
}
return -1;
}
Код:
/*
* если номер столбца равен номеру строчки по определению "дыры"
*/
public static int isSink()
{
int n = mat[0].lenght;
for (int i = 0; i < n; i++)
{
boolean flag = true;
if (mat[i,i] == 0)
{
for (int j = 0; j < n; j++)
{
if (i == j)
{
j++;
}
if (mat[i,j] == 1 || mat[j,i] == 0)
{
flag = false;
j = n;
}
}
if (flag)
return i;
}
}
return -1;
}
* если номер столбца равен номеру строчки по определению "дыры"
*/
public static int isSink()
{
int n = mat[0].lenght;
for (int i = 0; i < n; i++)
{
boolean flag = true;
if (mat[i,i] == 0)
{
for (int j = 0; j < n; j++)
{
if (i == j)
{
j++;
}
if (mat[i,j] == 1 || mat[j,i] == 0)
{
flag = false;
j = n;
}
}
if (flag)
return i;
}
}
return -1;
}
Код:
#include <iostream>
#include <ctime>
using namespace std;
int** setArray(int cellsPtr, int zeroLinePtr, bool flag);
void ouArray(int** arr, int cellPtr);
int searchHole(int** arr, int cellsPtr);
int main(int argc, char** argv[])
{
srand((unsigned)time(NULL));
/*случайное кол-во строк и столбцов, квадратная матрица*/
int cells = rand() % 4 + 4;
/*случайная строка, где будет принудительная дыра*/
int zeroLine = rand() % cells;
/*
Заполнения массива случайным образом
true = принудительно создаем дыру в случайном месте
false = заполнение случайной полседоваетльностью
*/
int** arr = setArray(cells, zeroLine, false);
cout << "Array:" << endl;
/*вывод массива в консоль*/
ouArray(arr, cells);
/*поиск дыры в массиве*/
cout << endl << "Rezult = " << searchHole(arr, cells) << endl;;
/*освобождение памяти*/
for (int idx = 0; idx < cells; idx++)
{
delete[] arr[idx];
}
delete[] arr;
cout << endl;
system("pause");
return 0;
}
int** setArray(int cellsPtr, int zeroLinePtr, bool flagPtr)
{
/*выделение памяти под массив*/
int** arr = new int*[cellsPtr];
for (int idx = 0; idx < cellsPtr; idx++)
{
arr[idx] = new int[cellsPtr];
}
if (flagPtr)
{
/*если истина, создаем принудительно в случайной строке, по значению из ZeroLine*/
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
/*заполняем все элементры строки 0*/
if (zeroLinePtr == idx)
{
arr[idx][jdx] = 0;
}
/*если строка не из zeroLine, заполняем случайно 0 или 1*/
else
{
arr[idx][jdx] = rand() % 2;
}
}
}
for (int idx = 0; idx < cellsPtr; idx++)
{
/*заполняем столбец 1, чтобы создать принудительно дыру по значению zeroLine*/
if (idx != zeroLinePtr)
{
arr[idx][zeroLinePtr] = 1;
}
}
}
else
{
/*случайное заполнение массива 0 или 1*/
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
arr[idx][jdx] = rand() % 2;
}
}
}
return arr;
}
void ouArray(int** arr, int cellsPtr)
{
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
cout << arr[idx][jdx]<< "t";
}
cout << endl;
}
}
int searchHole(int** arr, int cellsPtr)
{
/*флаг возрата функции 1 - дыра есть, -1 - дыры нет*/
int flag = 0;
/*флаг,показывающий что в строке, где дыра все 0*/
bool flagRow = false;
/*флаг,показывающий что в столбце, где дыра все 1*/
bool flagColumn = false;
/*индекс строки*/
int idxRow = 0;
/*индекс столбца*/
int idxColumn = 0;
for (int idx = 0; idx < cellsPtr; idx++)
{
/*проеряем строку на условия дыры, то есть все 0 встроке*/
if (arr[idx][idx] == 0)
{
flagRow = true;
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
idxRow = idx;
if (arr[idx][jdx] != 0)
{
flagRow = false;
break;
}
}
/*если строка прошла проверку, проверяем столбцы на дыру, чтобы все 1*/
if (flagRow)
{
flagColumn = true;
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
idxColumn = idx;
if (idx != jdx)
{
if (arr[jdx][idx] != 1)
{
flagColumn = false;
break;
}
}
}
}
}
/*находим первую дыру в матрице, поиск дальше с низкой вероятностью даст 2-у дыру*/
if (flagColumn)
break;
}
/*Сообщения о наличии дыры в матрице*/
if (flagColumn)
{
flag = 1;
cout << endl << "There is a hole." << endl;
cout << endl << "Index Row = " << idxRow << "; Index Column = " << idxColumn << endl;
}
else
{
flag = -1;
cout << endl << "There is no a hole." << endl;
}
return flag;
}
#include <ctime>
using namespace std;
int** setArray(int cellsPtr, int zeroLinePtr, bool flag);
void ouArray(int** arr, int cellPtr);
int searchHole(int** arr, int cellsPtr);
int main(int argc, char** argv[])
{
srand((unsigned)time(NULL));
/*случайное кол-во строк и столбцов, квадратная матрица*/
int cells = rand() % 4 + 4;
/*случайная строка, где будет принудительная дыра*/
int zeroLine = rand() % cells;
/*
Заполнения массива случайным образом
true = принудительно создаем дыру в случайном месте
false = заполнение случайной полседоваетльностью
*/
int** arr = setArray(cells, zeroLine, false);
cout << "Array:" << endl;
/*вывод массива в консоль*/
ouArray(arr, cells);
/*поиск дыры в массиве*/
cout << endl << "Rezult = " << searchHole(arr, cells) << endl;;
/*освобождение памяти*/
for (int idx = 0; idx < cells; idx++)
{
delete[] arr[idx];
}
delete[] arr;
cout << endl;
system("pause");
return 0;
}
int** setArray(int cellsPtr, int zeroLinePtr, bool flagPtr)
{
/*выделение памяти под массив*/
int** arr = new int*[cellsPtr];
for (int idx = 0; idx < cellsPtr; idx++)
{
arr[idx] = new int[cellsPtr];
}
if (flagPtr)
{
/*если истина, создаем принудительно в случайной строке, по значению из ZeroLine*/
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
/*заполняем все элементры строки 0*/
if (zeroLinePtr == idx)
{
arr[idx][jdx] = 0;
}
/*если строка не из zeroLine, заполняем случайно 0 или 1*/
else
{
arr[idx][jdx] = rand() % 2;
}
}
}
for (int idx = 0; idx < cellsPtr; idx++)
{
/*заполняем столбец 1, чтобы создать принудительно дыру по значению zeroLine*/
if (idx != zeroLinePtr)
{
arr[idx][zeroLinePtr] = 1;
}
}
}
else
{
/*случайное заполнение массива 0 или 1*/
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
arr[idx][jdx] = rand() % 2;
}
}
}
return arr;
}
void ouArray(int** arr, int cellsPtr)
{
for (int idx = 0; idx < cellsPtr; idx++)
{
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
cout << arr[idx][jdx]<< "t";
}
cout << endl;
}
}
int searchHole(int** arr, int cellsPtr)
{
/*флаг возрата функции 1 - дыра есть, -1 - дыры нет*/
int flag = 0;
/*флаг,показывающий что в строке, где дыра все 0*/
bool flagRow = false;
/*флаг,показывающий что в столбце, где дыра все 1*/
bool flagColumn = false;
/*индекс строки*/
int idxRow = 0;
/*индекс столбца*/
int idxColumn = 0;
for (int idx = 0; idx < cellsPtr; idx++)
{
/*проеряем строку на условия дыры, то есть все 0 встроке*/
if (arr[idx][idx] == 0)
{
flagRow = true;
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
idxRow = idx;
if (arr[idx][jdx] != 0)
{
flagRow = false;
break;
}
}
/*если строка прошла проверку, проверяем столбцы на дыру, чтобы все 1*/
if (flagRow)
{
flagColumn = true;
for (int jdx = 0; jdx < cellsPtr; jdx++)
{
idxColumn = idx;
if (idx != jdx)
{
if (arr[jdx][idx] != 1)
{
flagColumn = false;
break;
}
}
}
}
}
/*находим первую дыру в матрице, поиск дальше с низкой вероятностью даст 2-у дыру*/
if (flagColumn)
break;
}
/*Сообщения о наличии дыры в матрице*/
if (flagColumn)
{
flag = 1;
cout << endl << "There is a hole." << endl;
cout << endl << "Index Row = " << idxRow << "; Index Column = " << idxColumn << endl;
}
else
{
flag = -1;
cout << endl << "There is no a hole." << endl;
}
return flag;
}