status
Published
date
Jun 2, 2020
slug
summary
category
算法
tags

扩展问题:

  1. 写一个函数找出一个整数数组中,第k大的数(堆排序)

考虑的情况:

  1. 数组长度<2
  1. 数组元素全部相同
  1. 第二大值不止一个

代码实现:

  • 实现1:
    • /**
           * 实现: 返回第二大值
           * 1. 数组长度小于2,不存在第二大的值,返回-1
           * 2. 数组长度为2,返回两者中最小值
           * 3. 从前往后遍历一遍
           * 3.1 比最大值大,次大值变为最大值,最大值变为当前值
           * 3.2 只比次大值大,次大值变为当前值
           *
           * @param a
           * @return 第二大值
           */
          public static int max2(Integer[] a) {
              if (a.length == 2)
                  return a[0] > a[1] ? a[1] : a[0];
              else if (a.length > 2) {
                  int max1 = a[0] > a[1] ? a[0] : a[1];
                  int max2 = a[0] > a[1] ? a[1] : a[0];
                  for (int i = 2; i < a.length; i++) {
                      if (a[i] > max1) {
                          max2 = max1;
                          max1 = a[i];
                      } else if (a[i] > max2)
                          max2 = a[i];
                  }
                  return max2;
              }
              return -1;
          }
      
  • 实现2:先快排,再返回第二大的值

  • Cusdis
  • GitTalk