在Java中用ArrayList以升序插入对象

Question

因此，我来回尝试了很多次，尝试了多种不同的方法，但我似乎就是不能理解这种方法的适当算法。我正在创建一个多项式类，它使用一个ArrayList，其中( int coeff，int expo)系数是多项式的系数，expo是指数。在测试类中，我必须插入多个不同的术语对象，但它们需要按指数升序插入(例如，4x^1 + 2x^3 + x^4 + 5x^7)

这是我在insert()方法的末尾的代码，它有两个参数，coeff和expo：

public class Polynomial
{

   private ArrayList<Term> polynomials ;

   /**
     * Creates a new Polynomial object with no terms
     */
  public Polynomial()
  {
       polynomials = new ArrayList<>() ;
  }

  /**
    * Inserts a new term into its proper place in a Polynomial
    * @param coeff the coefficient of the new term
    * @param expo the exponent of the new term
    */
   public void insert(int coeff, int expo)
   {

      Term newTerm = new Term (coeff, expo) ; 


      if (polynomials.isEmpty())
      {
          polynomials.add(newTerm);
          return;
      }


      int polySize = polynomials.size() - 1 ;


      for (int i = 0 ; i <= polySize ; i++)
      {
            Term listTerm = polynomials.get(i) ;  
            int listTermExpo = listTerm.getExpo() ;

            if ( expo <= listTermExpo )
            {
                 polynomials.add(i, newTerm);
                 return;
            }

            else if ( expo > listTermExpo )
           {
                 polynomials.add(newTerm) ;
                 return ;
           }

    }

}

问题出现在代码的末尾。一旦我在索引中放入一个系数不是<=的项，它就会转到else if语句，并将其添加到列表的末尾。这是错误的，因为它需要被添加到它刚刚变得大于下一个系数的地方。仅仅因为它比这个系数大并不意味着它是最大的系数。我尝试反向执行for语句，其中：

for (i = polySize ; i >= 0 ; i--)
{
  etc.
}

但这也不起作用，因为它反过来也提出了同样的问题。如果有人能提供一些解决方案或答案，我将不胜感激，因为我非常困惑。在这一点上，我确信我只是把它搞得太复杂了。我只想知道如何识别指数较大，然后返回到for循环，直到它小于或等于索引的指数。

另外，我需要指出的是，我不允许使用任何其他集合或类，所以我必须使用for、if、else或do while语句来完成此操作。提前感谢！

Answer 1

从for循环中删除以下代码：

       else if (expo > listTermExpo)
       {
             polynomials.add(newTerm);
             return;
       }

将此代码放在for循环之后：

polynomials.add(newTerm);
return;

推理:仅当该术语不小于列表中的任何术语时，您才希望将该术语添加到列表末尾-而不仅仅是第一个术语。

此外，最好在语句后面紧跟着；，其间没有空格，而()s的内部不能紧跟任何空格。我已经编辑了我从你那里复制的代码，以表明我的意思。

Answer 2

这应该具有您指定的确切行为：

public void insert(int coeff, int expo) {
    Term newTerm = new Term(coeff, expo);
    int max = polynomials.size();
    int min = 0;
    int pivot;
    while (max > min) {
        pivot = (min + max) / 2;
        if (expo > polynomials.get(pivot).getExpo()){
            min = pivot + 1;
        }
        else {
            max = pivot;
        }
    }
    polynomials.add(min, newTerm);
}

如果列表中已经存在任何这样的术语，此算法将在第一个术语前面添加具有相同指数的新术语。