一、知识点:
双指针
二、文字分析:
使用两个指针 start 和 end 分别表示当前区间的起始位置和结束位置。遍历集合点编号数组时,如果当前集合点的编号与上一个集合点的编号连续,则更新当前区间的结束位置;否则,将当前区间的起始位置和结束位置加入结果中,并更新当前区间的起始位置和结束位置。最后,将最后一个区间的起始位置。
算法的时间复杂度为 O(n),空间复杂度为 O(m)。
三、编程语言:
java
四、正确代码:
import java.util.*;
public class Solution {
/**
* 找到覆盖所有编号的最小有序区间范围列表
*
* @param groups int整型一维数组,表示每头奶牛所在的集合点编号数组
* @param n int整型,表示集合点的总数
* @return int整型二维数组,表示连续整数区间范围列表
*/
public int[][] findGatheringAreas(int[] groups, int n) {
ArrayList<int[]> result = new ArrayList<>();
int start = groups[0]; // 当前区间的起始位置
int end = groups[0]; // 当前区间的结束位置
for (int i = 1; i < groups.length; i++) {
// 如果当前集合点的编号连续,则更新当前区间的结束位置
if (groups[i] == end + 1) {
end = groups[i];
} else {
// 否则,将当前区间的起始位置和结束位置加入结果中
result.add(new int[] {start, end});
// 更新当前区间的起始位置和结束位置
start = groups[i];
end = groups[i];
}
}
// 将最后一个区间的起始位置和结束位置加入结果中
result.add(new int[] {start, end});
// 将结果转换为二维数组并返回
return result.toArray(new int[result.size()][2]);
}
}

京公网安备 11010502036488号