Java实现TopK问题的方法

面试中会经常遇到手撕代码的情况,而求TopK的是经常遇到的题目。下面我就用Java来实现。主要通过两种方法实现,快排思想以及堆排序的思想,两者的复杂度为O(NlogK)。

基于快排的TopK实现:

import java.util.Arrays;

/**
 * 使用快排实现的TopK问题 Title: Description: Company:
 *
 * @author 郑伟
 * @date 2018年4月10日下午9:28:15
 */
public class TopK_PartitionSort {

  public static void main(String[] args) {

    int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };
    partitionSort(num, 0, num.length - 1, 3);
    System.out.println(Arrays.toString(num));
  }

  public static void partitionSort(int[] nums, int low, int high, int K) {
    if (low < high) {
      int pointKey = partitionSortCore(nums, low, high);
      if (K - 1 == pointKey)//TopK问题的核心,就是如果返回的下标为K-1,说明已经排序好了K个最大/最小的数,但是之间的顺序是不确定的
        return;
      partitionSort(nums, low, pointKey - 1, K);
      partitionSort(nums, pointKey + 1, high, K);
    }
  }

  /**
   * 快排的核心
   *
   * @param nums
   * @param low
   * @param high
   * @return 返回排序好以后的位置
   */
  public static int partitionSortCore(int[] nums, int low, int high) {
    // 以第一个座位标志位来比对
    int pivotkey = nums[low];
    while (low < high) {
      // 从pivotkey往最后一个位置比较
      while (low < high && pivotkey <= nums[high]) {
        --high;
      }
      // 开始交换pivotkey和nums[high]
      int temp = nums[low];
      nums[low] = nums[high];
      nums[high] = temp;
      // 此时nums[high]对应于pivotkey
      while (low < high && pivotkey >= nums[low]) {
        ++low;
      }
      // 找到比pivotkey大的书了,那就交换
      temp = nums[low];
      nums[low] = nums[high];
      nums[high] = temp;
      // 这时,pivotkey对应于nums[low]
    }
    return low;// 返回pivotkey对应的正确位置
  }

}

其实整个代码和快排一样,就是多了一个下标位置的判断,if (K - 1 == pointKey),这是核心,也就是为什么复杂度为NlogK。如果看不懂,可以先去理解快排的实现。

堆排序实现TopK:

/**
 * 使用堆排序实现的TopK问题 Title: Description: Company:
 *
 * @author 郑伟
 * @date 2018年4月11日上午9:28:15
 */
public class TopK_HeapSort {

  public static void main(String[] args) {
    int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };
    heapSort(num,3);
    System.out.println(Arrays.toString(num));
  }

  /**
   * 堆排序
   *
   * @param num
   */
  private static void heapSort(int[] num, int K) {
    for (int i = num.length / 2 - 1; i >= 0; i--) {
      adjustMin(num, i, num.length);// 调整0~num.length-1的数据
    }
    // 如果要实现topK,就在这里执行
    for (int j = num.length - 1; j >= 0 && K > 0; j--,K--) {
      // 交换最后一个
      swap(num, 0, j);
      // 再次调整0~j-1的数据
      adjustMin(num, 0, j);
    }
    //使用最大堆,K=3,输出[9, 7, 3, 2, 4, 1, 0, 17, 18, 20],最大的三个值17,18,20
    //使用最小堆,K=3,输出[3, 4, 9, 7, 20, 18, 17, 2, 1, 0],最小的三个值2,1,0
  }

  /**
   * 交换栈顶和最后一个元素
   *
   * @param num
   * @param i
   * @param j
   */
  private static void swap(int[] num, int i, int j) {
    int tem = num[i];
    num[i] = num[j];
    num[j] = tem;
  }

  /**
   * 调整为大顶堆
   *
   * @param num
   * @param root_index
   */
  private static void adjust(int[] num, int root_index, int length) {
    //
    int root = num[root_index];
    for (int j = root_index * 2 + 1; j < length; j = j * 2 + 1) {
      // 最大的儿子
      if (j + 1 < length && num[j] < num[j + 1]) {
        j = j + 1;// 指向了最大的儿子
      }
      if (root < num[j]) {
        num[root_index] = num[j];
        root_index = j;// 标记换了哪一个位置
      } else {
        break;// 已经是大顶堆了,不需要调整了
      }
    }
    num[root_index] = root;
  }

  /**
   * 小顶堆
   *
   * @param num
   * @param root_index
   * @param length
   */
  private static void adjustMin(int[] num, int root_index, int length) {
    //
    int rootValue = num[root_index];
    for (int k = root_index * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && num[k] > num[k + 1])
        k = k + 1;// K指向最小的子节点
      if (num[k] < rootValue) {
        num[root_index] = num[k];
        root_index = k;// 和k换了一下位置
      } else {
        break;// 本身不需要再调整了
      }
    }
    num[root_index] = rootValue;
  }
}

算法核心思想:与一般的堆排序不同的是,TopK只需要堆尾与堆顶交换K次就好,不需要全部交换一遍。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java实现TopK问题的方法

    面试中会经常遇到手撕代码的情况,而求TopK的是经常遇到的题目.下面我就用Java来实现.主要通过两种方法实现,快排思想以及堆排序的思想,两者的复杂度为O(NlogK). 基于快排的TopK实现: import java.util.Arrays; /** * 使用快排实现的TopK问题 Title: Description: Company: * * @author 郑伟 * @date 2018年4月10日下午9:28:15 */ public class TopK_PartitionSort

  • JAVA四种基本排序方法实例总结

    本文实例讲述了JAVA四种基本排序方法.分享给大家供大家参考.具体如下: JAVA四种基本排序,包括冒泡法,插入法,选择法,SHELL排序法.其中选择法是冒泡法的改进,SHELL排序法是 插入法的改进.所以从根本上来说可以归纳为两种不同的排序方法:即:插入法&冒泡法 一 插入法: 遍历排序集合,每到一个元素时,都要将这个元素与所有它之前的元素遍历比较一遍,让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置.交换是相邻遍历移动,双重循环控制实现.这种排序法属于地头蛇类型,在我的地牌上我要把

  • Java正则表达式提取字符的方法实例

    正好遇到一个需求需要将字符串中特定的字符全部提取出来,这个如果是按常规的字符串处理的话非常的繁琐.于是想到用正则表达式来完成.项目需求是这样的:需要提取车牌号中最后一个数字,比如说:苏A7865提取5,苏A876X提取6 实现方法: import java.util.regex.Matcher; import java.util.regex.Pattern; public class Test { public static void main(String[] args) { String s

  • Java实现MD5加密的方法

    本文实例讲述了Java实现MD5加密的方法.分享给大家供大家参考.具体实现方法如下: import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; public class MD5HashUtil { private MessageDigest md = null; private static MD5HashUtil md5 = null; private static final char

  • Java中Spring获取bean方法小结

    Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器框架,如何在程序中获取Spring配置的bean呢? Bean工厂(com.springframework.beans.factory.BeanFactory)是Spring框架最核心的接口,它提供了高级IoC的配置机制.BeanFactory使管理不同类型的Java对象成为可能,应用上下文(com.springframework.context.ApplicationContext)建立在BeanFactory基础之上,提供

  • Java使用JavaMail发送邮件的方法

    本文实例讲述了Java使用JavaMail发送邮件的方法.分享给大家供大家参考,具体如下: 代码一.Email_Autherticator.java 服务器验证代码 import javax.mail.Authenticator; import javax.mail.PasswordAuthentication; public class Email_Autherticator extends Authenticator { String username = "你邮箱的用户名"; S

  • Java中计算时间差的方法

    本文实例讲述了Java中计算时间差的方法.分享给大家供大家参考.具体如下: 假设现在是2004-03-26 13:31:40 过去是:2004-01-02 11:30:24 要获得两个日期差,差的形式为:XX天XX小时XX分XX秒 方法一: DateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); try { Date d1 = df.parse("2004-03-26 13:31:40"); Date

  • java 中enum的使用方法详解

    java 中enum的使用方法详解 enum 的全称为 enumeration, 是 JDK 1.5 中引入的新特性,存放在 java.lang 包中. 下面是我在使用 enum 过程中的一些经验和总结. 原始的接口定义常量 public interface IConstants { String MON = "Mon"; String TUE = "Tue"; String WED = "Wed"; String THU = "Thu

  • Java 读取外部资源的方法详解及实例代码

    Java 读取外部资源的方法详解 在Java代码中经常有读取外部资源的要求:如配置文件等等,通常会把配置文件放在classpath下或者在web项目中放在web-inf下. 1.从当前的工作目录中读取: try { BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("wkdir.txt"))); String str; while ((str = in.readLine())

  • 详解java.lang.reflect.Modifier.isInterface()方法

    详解java.lang.reflect.Modifier.isInterface()方法 java.lang.reflect.Modifier.isInterface(int mod)方法判断如果给定mod参数包含final修饰符,则返回true,否则返回false. 声明 以下是java.lang.reflect.Modifier.isInterface()方法的声明. public static boolean isInterface(int mod) 参数 mod - 一组修饰符. 返回值

随机推荐