We Learn   We Create   We Share

初学者指南
笔记
竞赛
关于我们
页面搜索

目录

AtCoder C 213

AtCoder

Leon | 09 Aug 2021

题目描述

题目会给你一个HxW的矩阵，并且该矩阵中只有n个元素拥有数值。在获得矩阵之后可以进行以下的操作：

如果有一列没有元素的话，则将其他的元素都向左移动一位；

如果有一行没有元素的话，则将所有的元素都向上移动一位；

打印出所有有效元素在进行操作之后的位置

思路

思路1：

前缀和数组：

用数组中的index来表示每一个元素的位置，数组中的内容是输出的时候，这一个行/列需要减去多少才是化简之后的位置。

但是这样会有一个问题，因为 \(1\le H,W\le 10^9\) 所以数组中的元素过多，直接导致了爆栈。

思路2

本质上是思路一的改进方法：

因为上一个方法发生了爆栈的情况，所以第二个方法不用数组中的index来表示行或列，直接使用两个数组来表示每一个行/列需要减去多少。因为这样子可以大大的减小空间。具体求出每一个行/列需要减去的数量 \(f(n) = row(n)-row(n-1)+f(n-1)\)

并将这些所有的行/列需要减去的数量都一一对应储存到两个Hashmap里面，最后在输出的时候直接提取这个数就好了。这一步主要是降低复杂度，如果不将这些数放进Hashmap中就需要用O(N^2)的复杂度来输出，只是放到Hashmap里只需要O(N)的复杂度，提取时只要O(1)的复杂度。

复杂度分析：

将所有的数放进数组里: \(O(N)\) 将两个数组进行排序: \(O(N\log N)\) 将所有的需要减去的数算出来: \(O(N)\) 放进Hashmap里: \(O(N)\) 最后输出的收提取Hashmap里面的数: \(O(1)\) 所以整体复杂度为： \(O(N\log N)\)

代码实现

import java.util.*;
public class reorder{
    public static void main(String [] args){
        Scanner in = new Scanner(System.in);
        int h = in.nextInt();
        int w = in.nextInt();
        int n = in.nextInt();
        HashSet<Integer>row = new HashSet<Integer>();
        HashSet<Integer>col = new HashSet<Integer>();
        oneDot [] coordinate = new oneDot [n];
        for (int i = 0; i < n; i++) {
            int theRow = in.nextInt()-1;
            int theCol = in.nextInt()-1;
            row.add(theRow);
            col.add(theCol);
            coordinate[i] = new oneDot(theRow, theCol);
        }

        int rownum = row.size();
        int colnum = col.size();
        int [] rows = new int [rownum];
        int [] cols = new int [colnum];
        int index = 0;

        for(int oneRow:row){
            rows[index] = oneRow;
            index++;
        }
        index = 0;
        Arrays.sort(rows);
        for(int oneCol:col){
            cols[index] = oneCol;
            index++;
        }
        Arrays.sort(cols);
        int [] rowm = new int [rownum];
        int [] colm = new int [colnum];
        rowm[0] = rows[0]-0;
        for (int i = 1; i < rowm.length; i++) {
            rowm[i] = rows[i]-rows[i-1]+rowm[i-1]-1;
        }
        colm[0] = cols[0]-0;
        for (int i = 1; i < colm.length; i++) {
            colm[i] = cols[i]-cols[i-1]+colm[i-1]-1;
        }


        HashMap <Integer,Integer> rowminus= new HashMap<Integer,Integer>();
        HashMap <Integer,Integer> colminus= new HashMap<Integer,Integer>();
        for (int i = 0; i < rowm.length; i++) {
            rowminus.put(rows[i], rowm[i]);
        }
        for (int i = 0; i < colm.length; i++) {
            colminus.put(cols[i], colm[i]);
        }


        for (int i = 0; i < coordinate.length; i++) {
            System.out.println((coordinate[i].row-rowminus.get(coordinate[i].row)+1)+" "+((coordinate[i].col-colminus.get(coordinate[i].col))+1));
        }
    }
}
class oneDot{
    int row;
    int col;
    public oneDot(int row,int col){
        this.row = row;
        this.col = col;
    }
}

评论区