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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| import java.util.*;
import java.security.SecureRandom;
/**
* Задача поиска специальных элементов в строке матрицы. Специальными являются элементы строки,
* которые больше любого элемента, расположенного слева от себя и меньше любого элемента,
* расположенного справа.
*/
public class SpecialElements {
// Матрица.
private byte [][] matrix;
/**
* Конструктор, создающий новую матрицу заданных размеров.
* @param width ширина матрицы.
* @param height высота матрицы.
*/
public SpecialElements(int width, int height) {
matrix = new byte[height][width];
SecureRandom random = new SecureRandom();
for (byte[] row : matrix)
random.nextBytes(row);
}
/**
* Производит поиск специальных элементов и возвращает их.
* @return ассоциативный массив, ключами которого являются номера строк, в которых найдены
* специальные элементы, значениями - множество этих элементов.
*/
public TreeMap<Integer, Set<Byte>> specialElements() {
TreeMap<Integer, Set <Byte>> result = new TreeMap<Integer, Set<Byte>>();
Set<Byte> elements;
byte temp = 0;
for (int r = 0; r < matrix.length; r++) {
byte[] row = matrix[r];
elements = new HashSet<Byte>();
// Идем слева направо и добавляем во множество элементы, большие тех, что слева от них.
for(byte element : row) {
if(element > temp) {
elements.add(element);
temp = element;
}
}
// Идем справа налево и удаляем из множества элементы, большие тех, что справа от них.
for(int i = row.length - 1; i >= 0; i--) {
byte element = row[i];
if(element > temp)
elements.remove(element);
else
temp = element;
}
// Сохраняем результат при наличии хотя бы одного специального элемента в строке.
if(elements.size() > 0)
result.put(r, elements);
temp = 0;
}
return result;
}
/**
* Производит поиск специальных элементов и возвращает их количество.
* @return количество специальных элементов.
*/
public int specialElementsCount() {
int result = 0;
Set<Byte> elements = new HashSet<Byte>();
byte temp = 0;
for(byte[] row : matrix) {
// Идем слева направо и добавляем во множество элементы, большие тех, что слева от них.
for(byte element : row) {
if(element > temp) {
elements.add(element);
temp = element;
}
}
// Идем справа налево и удаляем из множества элементы, большие тех, что справа от них.
for(int i = row.length - 1; i >= 0; i--) {
byte element = row[i];
if(element > temp)
elements.remove(element);
else
temp = element;
}
// Добавляем к результату количество элементов, найденных в строке.
result += elements.size();
elements.clear();
temp = 0;
}
return result;
}
/**
* Возвращает строковое представление матрицы этого объекта.
* @return строковое представление матрицы.
*/
@Override
public String toString() {
StringBuffer result = new StringBuffer(matrix.length * matrix[0].length * 6);
StringBuffer buffer;
for (byte[] row : matrix) {
for (byte element : row) {
buffer = new StringBuffer(5);
buffer.append(element);
while(buffer.length() != 5)
buffer.insert(0, " ");
result.append(buffer);
}
result.append("\n");
}
return result.toString();
}
/**
* Испытания на прочность.
* @param args аргументы командной строки.
*/
public static void main(String[] args) {
SpecialElements task = new SpecialElements(100, 100);
System.out.println("Matrix:");
System.out.println(task.toString());
int count = 0;
System.out.println("Answer: ");
for (Map.Entry<Integer,Set<Byte>> entry : task.specialElements().entrySet()) {
System.out.println("Row #" + entry.getKey() + ": " + entry.getValue().toString());
count += entry.getValue().size();
}
System.out.println(count + " element(s) found.");
}
} |
(
Сообщение от sisi11
