查找符号中第二大键的函数 table

Question

所以我正在编写一个函数，该函数将使用链表实现找到无序符号 table 中的第二大键，到目前为止我的代码无法正常工作，想知道是否有人有任何提示谢谢！

public Key secondLargestKey () {
          if(first == null) return null;
          if(size()<=1)  return null;
          Node secondMax=null;
          Node Max=first;
           for (Node pointer=first.next;pointer.next!=null;pointer=pointer.next) {
              if(Max.key.compareTo(pointer.key)<=0) {
                 secondMax=Max;
                 Max=pointer.next; 
               }
              else {
                 secondMax=Max.next;
                 Max=pointer; 
              }

              }   
            return Max.key;
        }`

输出：

secondLargestKeyTest: Correct  String  Answer: null
secondLargestKeyTest: Correct  String A Answer: null
secondLargestKeyTest: *Error*  String AB Expected A Actual: B
secondLargestKeyTest: Correct  String ABC Actual: B
secondLargestKeyTest: Correct  String ABABABC Actual: B
secondLargestKeyTest: *Error*  String ZAYBXC Expected Y Actual: Z

Answer 1

您的代码接近正确。 for 循环中的终止条件需要检查 pointer!=null，而不是 pointer.next!=null。此外，如果 pointer.key 小于 Max，则需要将其与 secondMax 进行比较，如果更大则接受它，或者 secondMax 是 null（即尚未设置）

这里有一些代码供参考：

static <E extends Comparable<E>> E secondMax(Node<E> head)
{
  if(head == null) return null;

  E max2 = null;
  E max1 = head.key;
  for(Node<E> curr=head.next; curr!=null; curr=curr.next)
  {
    if(curr.key.compareTo(max1) >= 0)
    {
      max2 = max1;
      max1 = curr.key;
    }
    else if(max2 == null || curr.key.compareTo(max2) > 0)
    {
      max2 = curr.key;
    }
  }
  return max2;
}

static class Node<E>
{
  E key;
  Node<E> next;
  public Node(E k)
  {
    key = k;
  }
}

查找符号中第二大键的函数 table

Function to find the second largest key in a symbol table

java

linked-list

key-value

symbol-table