Java 8:如何找到最小、有效的kth

Question

在java 8中，如何有效地找到最小的Kth？最小的是

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

我在下面试过了。如果有一个更有效的解决方案，提供Java-8的安全性，比如我不应该在访问索引之前检查大小，以防出现空数组等等。我相信我自己的解决方案是安全的。

如果存在可证明的时间复杂度比较方法，我的Java-8方法的和更好的Java-8方法将是值得赞赏的。谢谢。

package lab.rat.jerry.kthsmallest;

import static java.util.stream.Collectors.toList;

import java.util.Arrays;
import java.util.List;

public class KthSmallest {

    // Inputs
    static int k = 3;

    static Integer[] myIntArray = {2, 3, 1, 4, -2, 0, -3, 0, -1, 5 };

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(myIntArray);

        System.out.println(list
            .stream()
            .sorted()
            .distinct()
            .limit(k)
            .skip(k-1)
            .collect(toList())
            );
    }
}

Answer 1

您可以在Java中使用简单的数据结构PrioretyQueue。您可以快速获取并移除最大或最小的元素：

public static int kthLargestElement(int[] nums, int k) {

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i = 0; i < nums.length ; i++) {
        queue.add(nums[i]);
    }
    while (k > 1){
        queue.poll();
        k-=1;
    }
    return queue.poll();
}

Answer 2

我不知道这样做的效率有多高，但考虑到以下情况：

1. 数组包含重复的值。
2. K大于最后的列表。

      int k = 4;
      int[] numbs = { 1, 2, 3, 3, 3, 3, 3, 3,10,11,12
      };

      int smallest =
            Arrays.stream(numbs).distinct().sorted().skip(k - 1).limit(
                  1).findFirst().orElse(Integer.MIN_VALUE);

      System.out.println(smallest);

1. 这会将数组转换为流。
2. 移除重复项
3. 整理剩下的东西。
4. 跳过第一个k-1值。
5. 将列表的其余部分限制为一个
6. 还回来。

如果k太大，则返回最小int值。

Answer 3

你可以试试这个：

package lab.rat.jerry.kthsmallest;

import java.util.Arrays;
import java.util.List;

public class KthSmallest {

       // Inputs
      static int k = 3;

      static Integer[] myIntArray = {2, 3, 1, 4, -2, 0, -3, 0, -1, 5 };

      public static void main(String[] args) {

         List<Integer> list = Arrays.asList(myIntArray);

         int smallest = list.stream()
                            .mapToInt(Integer::intValue)
                            .sorted()
                            .limit(k)
                            .skip(k-1)
                            .findFist()
                            .getAsInt();
         System.out.println(smallest);
     }
}

通过使用这种方法，您可以避免NullPointerException。因为findFist()将返回可选的。

希望能有所帮助:)