Суммируйте элементы в отсортированном списке, а затем добавляйте суммированное значение в список

Question

Итак, вот моя проблема, у меня есть список, который содержит что-то вроде этого [4,7,8,23,41] Что я хочу это 4 + 7 = 11, поэтому 11 следует добавить в этот список, а 4 и 7 следует удалить. затем 11 +8 = 19, поэтому добавлено 19, а 11 и 8 следует удалить.

  int finalSum=0;
  Collections.sort(myList);

  for(int i =0;i<myList.size();i++)
  {
      for(int j=i+1;i<myList.size();j++)
      {
          int sum = myList.get(i) + myList.get(j);
          myList.remove(i);
          myList.remove(j);
      }
  }

  for(int k=0;k<myList.size();k++)
  {
       finalSum += myList.get(k); 
  }

Answer 1

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

for(int k=0;k<myList.size();k++)
{
   finalSum += myList.get(k); 
}

Но, как вы описали, вы хотите добавить первые два числа из списка, а затем удалить их, добавить итог обратно в список и выполнить тот же процесс, тогда мы можем использовать PriorityQueue здесь. Это может помочь отследить возрастающий порядок, и в любом случае временная сложность для нашего кода будет O (n logn), где n - размер списка.

    PriorityQueue<Integer> pq= new PriorityQueue<>(); // by default it maintains the ascending order
    for(int k=0;k<myList.size();k++){
        pq.add(myList.get(k));
    }
    while(pq.size()>1){
        int num1 = pq.poll(); // taking out first smallest number
        int num2 = pq.poll(); // taking out second smallest number
        pq.add(num1+num2);
    }
    finalSum = pq.poll(); // final sum

Answer 2

Я не уверен, по какой причине вам нужен такой алгоритм, однако он должен вести себя так, как вы описали.

public static void main(String[] args) {
    List<Integer> myList = new LinkedList<>(Arrays.asList(4,7,8,23,41));
    Collections.sort(myList);
    while (myList.size() > 1) {
        myList.add(0, myList.remove(0) + myList.remove(0));
    }
    int finalSum = myList.get(0);
    System.out.println(finalSum);
}

Лучшим подходом для суммирования элементов в списке будет:

public static void main(String[] args) {
    List<Integer> myList = Arrays.asList(4,7,8,23,41);
    int finalSum = myList.stream().reduce(0, Integer::sum);
    System.out.println(finalSum);
}

Answer 3

Поскольку вы продолжаете удалять элементы из списка, вы можете продолжать использовать индекс 0.

      List<Integer> list = new ArrayList<>(Arrays.asList(4,7,8,23,41));

      int first = 0;
      while (list.size() > 0) {
         int v = list.remove(0) + first;
         list.add(0, v);
         System.out.println(list);
         first = list.remove(0);
      }

Но если вам нужна только сумма, это проще всего.

      int sum = list.stream().mapToInt(a -> a).sum();