一、知识点:
双指针
二、文字分析:
使用两个指针 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]); } }