LC874的复杂度分析
bobo老师你好，我不大确定我用Java实现的LC874题的复杂度分析是否正确，请问老师能否帮忙过目下我这道题的复杂度分析？（代码附在下面）谢谢老师。
这道题需要开辟一个长度为obstacle数组的set，所以空间复杂度为O(len(obs))。对于时间复杂度，首先我们要遍历一遍obstacle数组，把所有元素放入set (这是O(len(obs)))，然后我们要遍历commands数组 (这是O(len(comm)))，考虑每一个具体执行的command（要么改变direction，要么沿着一个方向行走），这里的复杂度为O(1)（花时间最多的是行走9步的操作，就是O(9)），然后我们还要判断下一步是否是obstacle（如果用HashSet查找则是O(1)）。
因此总体时间复杂度为O(len(obs) + 9 * len(commands)) = O(len(obs) + len(commands))。下面是代码（实现稍微复杂了一点），谢谢老师！
public class Solution {
private HashMap<Pair<Integer, Integer>, Pair<Pair<Integer, Integer>, Pair<Integer, Integer>>> dir_map;
private HashSet<Pair<Integer, Integer>> obs_pos;
private Pair<Integer, Integer> cur_dir;
private Pair<Integer, Integer> cur_pos;
private int max_dist;
public int robotSim(int[] commands, int[][] obstacles) {
// include the left, right direction of a direction
dir_map = new HashMap<>();
dir_map.put(new Pair<>(0,1), new Pair<>(new Pair<>(-1,0), new Pair<>(1,0)));
dir_map.put(new Pair<>(0,-1), new Pair<>(new Pair<>(1,0), new Pair<>(-1,0)));
dir_map.put(new Pair<>(1,0), new Pair<>(new Pair<>(0,1), new Pair<>(0,-1)));
dir_map.put(new Pair<>(-1,0), new Pair<>(new Pair<>(0,-1), new Pair<>(0,1)));
obs_pos = new HashSet<>();
for(int i=0; i<obstacles.length; i++){
obs_pos.add(new Pair<>(obstacles[i][0], obstacles[i][1]));
}
cur_dir = new Pair<>(0,1);
cur_pos = new Pair<>(0,0);
max_dist = 0;
for(int command: commands){
next_Step(command);
}
return max_dist;
}
// return the position of a next step
private void next_Step(int command){
if(command == 0 || command > 9 || command < -2) throw new IllegalArgumentException("Invalid command");
if(command == -2){
cur_dir = dir_map.get(cur_dir).getKey();
}
else if(command == -1){
cur_dir = dir_map.get(cur_dir).getValue();
}
else{
int counter = 0;
while (counter != command){
int next_x = cur_pos.getKey() + cur_dir.getKey();
int next_y = cur_pos.getValue() + cur_dir.getValue();
if(!obs_pos.contains(new Pair<>(next_x, next_y))){
cur_pos = new Pair<>(next_x, next_y);
}
counter++;
}
}
max_dist = Math.max(max_dist, cur_pos.getKey() * cur_pos.getKey() + cur_pos.getValue() * cur_pos.getValue());
}
722
收起
