Блог

Главная - Вопросы по программированию - Объединить интервалы в одном цикле for

Объединить интервалы в одном цикле for

#java #algorithm #arraylist #merge #array-merge

#java #алгоритм #arraylist #слияние #массив-слияние

Вопрос:

Это может быть странный вопрос, но я пытаюсь объединить интервалы времени, и меня просто беспокоит, что за пределами цикла for есть одна строка — я действительно хочу объединить эту строку (ха-ха.) в цикл for, и все произойдет сразу.

Проблема: скажем, например, вам заданы интервалы (1, 5), (3, 7), (4, 6), (6, 8), (10, 12), (12, 15) программа должна вернуть (1,8),(10,15), так как они объединяют всеперекрывающиеся интервалы.

Мой подход заключается в том, что у меня есть текущее значение со значениями первой пары, затем я запускаю цикл for от 1 до конца и проверяю, сливается ли пара, в которой я нахожусь, с моей текущей или нет. Если он сливается, я обновляю значения в моей текущей паре, и если он не сливается, я добавляю current в свой список результатов, а затем обновляю его значения до любого узла, на котором я сейчас нахожусь.

Не стесняйтесь изменять код, если это необходимо, чтобы все это работало в одном цикле for. Если вы видите какие-либо другие ошибки в коде, пожалуйста, дайте мне знать. Спасибо!

 class Pair{
    public int first;
    public int second;
    
    public Pair(int x, int y){
      this.first = x;
      this.second = y; 
    }
}

class MergeIntervals{
  static ArrayList<Pair> mergeIntervals(ArrayList<Pair> v) {
  ArrayList<Pair> result = new ArrayList<Pair>();
 
  //check for size amp; null
  if(v == null || v.size() == 0) {
    return null;
  } 
  if(v.size() == 0) {
    result.add(v.get(0));
    return resu<
  }

  Pair current = new Pair(v.get(0).first, v.get(0).second);

  for(int i = 1; i < v.size(); i  ) {

    //want to merge
    if(v.get(i).first < current.second) {
      if(v.get(i).second > current.second) {
        current.second = v.get(i).second;
      }
    }
    else {
      result.add(new Pair(current.first, current.second));
      current.first = v.get(i).first;
      current.second = v.get(i).second;
    }
  }
  //loop broke before was able to merge
  result.add(new Pair(current.first, current.second));

  return resu<
  }
}

Комментарии:

1. Сразу после комментария «Хочу объединить», вероятно, это должно быть <=, а не < .

2. Кроме того, если size == 1, вы добавляете элемент 0, а не if size == 0, который может быть заменен на v.isEmpty() в if перед ним.

3. И, наконец, вы можете просто добавить current в конце, поскольку он больше не изменяется. Если вы хотите, чтобы это было в цикле, чего я бы не рекомендовал, просто добавьте if(i == v.size() — 1) перед ним и поместите его в конец цикла, но тогда вы также можете прервать после добавления последнего элемента в if и удалить i < v.size() из for . В противном случае вы в основном проверяете одно и то же дважды.

4. Когда (v.get(i).first < current.second) вы должны расширить оба конца: current.first = Math.min(current.first, v.get(i).first); current.second = Math.max(current.second, v.get(i).second);

Ответ №1:

Для обобщения возможных изменений / улучшений существующего кода:

  • в классе Pair предоставьте конструктор копирования и переопределите toString() для удобства
  • улучшите проверку входных данных в merge методе
  • отсортируйте входные данные, чтобы гарантировать порядок интервалов
  • используйте Pair конструктор копирования в merge методе
 class Pair{
    public int first;
    public int second;
    
    public Pair(int x, int y){
        this.first = x;
        this.second = y; 
    }
    
    public Pair(Pair p) {
        this(p.first, p.second);
    }
    
    @Override
    public String toString() {
        return "("   first   ", "   second   ")";
    }
}

class MergeIntervals{
    public static List<Pair> merge(List<Pair> v) {
        if (null == v) {
            return null;
        }
        // early return an empty list or containing a single pair
        if (v.size() < 1) {
            return v;
        }
        List<Pair> result = new ArrayList<>();
        
        Collections.sort(v, (a, b) -> Integer.compare(a.first, b.first));
        
        Pair current = new Pair(v.get(0));
        
        for (int i = 1; i < v.size(); i  ) {
            Pair p = v.get(i);
            if (p.first <= current.second) {
                current.second = Math.max(p.second, current.second);
            } else {
                result.add(current);
                current = new Pair(p);
            }
        }
        result.add(current);

        return resu<
    }
}

Тест:

 List<Pair> data = Arrays.asList(
    new Pair(3, 7),
    new Pair(1, 5),
    new Pair(6, 8),
    new Pair(4, 6),
    new Pair(10, 12),
    new Pair(12, 15)
);

System.out.println(MergeIntervals.merge(data));

Вывод:

 [(1, 8), (10, 15)]