计算Java矩阵中未访问的单元格 [英] Count the cells which are not visited in matrix in Java

问题描述

我有N x M矩阵，其中N是行数，M是列数. 我必须执行t任务. 每个任务都包含row，column_1，column_2.这意味着现在已访问给定行的column_1到column_2(含)之间的单元格.

I have N x M matrix where N is number of rows and M is number of columns. I have to perform t tasks. Each task contains row,column_1,column_2. It means that the cell between column_1 to column_2(inclusive) of given row are now visited.

例如:

任务1、2、3、6表示现在已访问第2行中的单元3至6.

task 1: 2,3,6 means that cells 3 to 6 are now visited cell in row 2.

假设我有4 x 4矩阵，我有3个任务.

Suppose, I have 4 x 4 matrix and I have 3 tasks.

任务1:3、2、3

任务2:2,1,3

任务3:3 1,3

因此，现在未访问的单元数为10(任务可以包括先前访问的单元号).

So, now number of cells which are not visited are 10. (tasks can include cell number which are previously visited).

我必须计算未访问的单元格. 由于N和M可以在1到10 ^ 9之间，所以我无法解决问题. 我解决了Java中N和M较小但无法解决较大输入的问题(任务不会超过1000个)

I have to count the cells which are not visited. Since N and M can be between 1 and 10^9, I am unable to solve the problem. I have solved the problem when N and M are smaller in java but couldn't solve for larger input.(Tasks will not be more than 1000)

我不是要代码，但是有人可以给我优化方法来解决这个问题吗?

I am not asking for code but can anyone just give me optimize approach to solve this problem ?

输入将像(对于给定的示例):

Edit 1: input will be like(for given example):

4 4 3

3 2 3

2 1 3

3 1 3

第一行分别表示N M t.因此，N ＝ 4，M ＝ 4并且t ＝ 3. 接下来的t行将分别显示第column_1列和第_2列.

First line indicates N M t respectively. Hence N=4, M=4 and t=3. Next t lines will show row column_1 column_2 respectively.

推荐答案

以下是解决方案的概述(无需代码).

Here is an outline of a solution (no code as required).

首先，请注意，我们可以分别解决每一行的任务. 此外，只有具有至少一个实际输入内容的行才完全不被访问. 因此，第一步将是将有关每一行的信息存储在一起. 我会使用从行号到属于该行的输入列表的映射. 首先，将整个输入读入此类映射. 然后，遍历地图并为每个受影响的行解决任务.

First, note that we can solve the task for each row separately. Moreover, only the rows with at least one actual input matter, others are completely not visited. So, the first step will be to store the information regarding each row together. I'd use a map from row-number to the list of inputs which belong to that row. First, read the entire input into such map. Then, iterate over the map and solve the task for each individual affected row.

接下来，我们在一行中有一个简单的版本. 一行上有一些线段，我们想知道它们的并集的总长度. 这可以通过以下方式解决. 而不是自己存储段，而是为每个段创建两个 event :段从例如坐标 x ₁ 开始，而段在坐标 x处结束 ₂ . 现在，根据所有事件的 x 坐标对其进行排序，并以排序的顺序对其进行迭代，以保持当前打开但未关闭的段数. 对于打开事件，计数更改为+1，对于关闭事件，计数更改为-1. 在坐标为 x _prev 和 x _next 的两个连续事件之间，如果计数为非零，则添加 x _next -答案的x _上一个 . 否则，不添加任何内容. 最后，答案是该行中各段的并集的总长度.

Next, we have a simpler version in one row. There are some segments on a line, and we want to know the total length of their union. This can be solved in the following way. Instead of storing segments themselves, create two events for each segment: segment start at say coordinate x₁ and segment end at coordinate x₂. Now, sort all events by their x-coordinate, and iterate over them in sorted order, maintaining the count of segments currently opened but not closed. For an open event, the count changes by +1, and for a close event, it changes by -1. Between two consecutive events at coordinates x_prev and x_next, if the count is non-zero, add x_next - x_prev to the answer. Otherwise, add nothing. In the end, the answer is the total length of the union of the segments in the row.

由于排序事件，具有 k 的每一行的复杂度为 O(k log(k)). 因此，总复杂度为 O(t log(t))，其中 t 是输入数量，因为所有 k 的总和为 t ，最糟糕的情况是所有输入都影响同一行. 坐标不会影响复杂性. 但是，请确保选择适当的数据类型:例如，对于N = M = 10 ⁹ 的答案可以是10 ¹⁸ 的阶数，因此我们必须在long代替int.

The complexity in each row with k is O(k log(k)) because of sorting events. The total complexity is therefore O(t log(t)) where t is the number of inputs, since the sum of all k is t, and the worst case is when all inputs affect the same row. The coordinates don't affect the complexity. However, be sure to choose appropriate data types: for example, the answer for N = M = 10⁹ can be of order 10¹⁸, so we have to perform calculations in a long instead of int.

这篇关于计算Java矩阵中未访问的单元格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！