java返回最小的元素。

From an array int[] a, I want to find and return an array with k.length containing the k smallest elements sorted.

从数组int[] a中，我想查找并返回一个带有k的数组。长度包含k最小元素排序。

There cant be any changing of the content of array a. After making a helping array of k.length I copy the k first values from a, then sorting it.

数组a的内容不可能有任何变化。我从a复制k的第一个值，然后对它进行排序。

After this if there is any elements in array a that is smaller than the ones in the help ing array I put it in the right position and the last element disappear and so on.

在这之后，如果数组a中有任何元素小于帮助数组中的元素我把它放在正确的位置，最后一个元素消失，等等。

Method:

方法:

public static int[] kMinst(int[] a, int k)

Possible Input:

可能的输入:

int[] a = {1,2,3,4,5,6,7,8,9,10}
kMinst(a, a.length);

Output:

输出:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Another input:

另一个输入:

int[] b = {4,3,2,1}
kMinst(b, 3);

Output:

输出:

[1, 2, 3]

What I have so far. And it's not working and is too inefficient:

到目前为止。它不工作而且效率太低:

public static int[] kMinst(int[] a, int k) {

    if (k < 1 || k > a.length) {
        throw new IllegalArgumentException("k har ikke riktig verdi!");
    }

    int[] verdier = new int[k];

    for (int i = 0; i < verdier.length; i++) {
        verdier[i] = a[i];
    }
    sortering(verdier);

    for (int i = verdier.length; i < a.length; i++) {
        for (int j = verdier.length - 1; j > 0; j --) {
            if (a[i] < a[j]) {
                int temp = a[j];
                for (int l = verdier.length - 1; l > j; l--) {
                    a[l] = a[l - 1];
                }
                a[j] = temp;
            }
        }
    }

    return verdier;
}

6 个解决方案

#1

You could build a heap from your original data which will be O(nlogn) and then get k elements from that heap which would also be O(nlogn) in the worst case.

您可以从原始数据中构建一个堆，它将是O(nlogn)，然后从这个堆中获取k个元素，在最坏的情况下也会是O(nlogn)。

#2

You can sort the array, and get the first k elements from it.

您可以对数组进行排序，并从中获取第一个k元素。

    public static int[] kMinst(int[] a, int k){
    if (k < 1 || k > a.length) {
        throw new IllegalArgumentException("k need to be greater than 1 and lesser than the length of the array");
    }
    int help[] = new int[a.length];
    int res[] = new int[k];
    for(int i = 0; i < a.length; i++) help[i] = a[i]; // copy the a array, not to change it
    Arrays.sort(help);
    for(int i = 0; i < k; i++) res[i] = help[i]; // get the first k elements from the sorted array
    return res;
}

Hope it helps :)

希望它能帮助:)

#3

I guess the below code serves ur purpose,

我想下面的代码符合你的目的，

public class SortArray {

公开课SortArray {

public int[] sort(int[] a,int b) {
    int c[]=new int[b];
    int temp=0;
 for (int i = 1; i < a.length; i++) {

for (int j = 0; j < i; j++) {
    if(a[i] <=a[j]){
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;      
    }
  }
}
 for (int i = 0; i < b; i++) {
  c[i]=a[i];    
      }
return c;
}


public static void main(String[] args) {
    int a[]={7,2,4,5,3,7};
    SortArray sort=new SortArray();
    int[] c=sort.sort(a,3);
    for (int i = 0; i < c.length; i++) {
        System.out.println(c[i]);
    }

}
}

#4

I'd use a Set to discard duplicates and make it a TreeSet so it does all of the sorting itself.

我将使用一个集合来丢弃副本，使它成为TreeSet，这样它就完成了所有的排序工作。

public static Integer[] kSmallest(Integer[] a, int k) {
    // Use a TreeSet to keep tbhe smallest.
    TreeSet<Integer> kSmallest = new TreeSet<Integer>();
    // Fold all the array into the set.
    for (Integer x : a) {
        // Add it in.
        kSmallest.add(x);
        // Trim to k.
        if (kSmallest.size() > k) {
            Iterator<Integer> last = kSmallest.descendingIterator();
            // Select the biggest.
            last.next();
            // Remove it.
            last.remove();
        }
    }
    // Make my result.
    return kSmallest.toArray(new Integer[0]);
}

#5

Here is an implementation which finds Kth minimum element in an array containing unique elements. If you want to allow duplicates, you can use java.util.Set to eliminate duplicates. It is based on randomized Quick Select algorithm and has worst case in order of n. It outputs unordered sequence of K number of smallest elements from the original array.

这里是一个实现，它在包含独特元素的数组中找到第k个最小元素。如果要允许重复，可以使用java.util。消除重复。它以随机快速选择算法为基础，以n为最坏的情况，它从原始数组输出K个最小元素的无序序列。

First it finds index of Kth smallest elemnt as well as does partial unordered sorting with respect to list[k]. Therefore, at the end result would contain K numbers which are smaller in the array with the Kth smallest element at the right most position.

首先，它发现了Kth最小元素的索引，以及对list[k]的部分无序排序。因此，最终的结果将包含K个数字，其在数组中较小，而第K个最小的元素位于最右边的位置。

 public class QuickSelect {

    public static void main (String[] args) {
        final int[] list = new int[]{1,2,11,16,34,3,4,42,5,6,28,7,8,9,10};
        QuickSelect qs = new QuickSelect();
        final int k = 10;
        final int kthMinIndex = qs.findKthMinimum (list, k - 1);
        System.out.println("[");
        for (int i = 0; i <= kthMinIndex; i++)
            System.out.print(list[i] + " ");
        System.out.print("]");

    }

    public int findKthMinimum (final int[] list, final int k) {
        if (k > list.length || k < 1) {
            throw new IllegalArgumentException("Bad arguments.");
        }
        final int left = 0;
        final int right = list.length - 1;
        final int pivot = (int)Math.floor((double)left +  (Math.random() * (double)(right - left)));
        final int result = findKthMinimum (list, left, right, k , pivot);
        return result;
    }

    private int findKthMinimum (final int[] list, int left, int right, final int k, int pivot) {
        int partitionElement = partition (list, left, right, pivot);
        while (left != right) {
            if (partitionElement == k)
                break;
            else if (partitionElement > k) {
                right = partitionElement - 1;
                pivot = (int)Math.floor((double)left +  (Math.random() * (double)(right - left)));
            } else if (partitionElement < k) {
                left = partitionElement + 1;
                pivot = (int)Math.floor((double)left +  (Math.random() * (double)(right - left)));
            }
            partitionElement = partition (list, left, right, pivot);
        }
        return list[partitionElement];
    }

    private int partition (final int[] list, int left, int right, int pivot) {
        final int pivotElement = list[pivot];
        swap (list, pivot, right);
        int lastStoredIndex = left;
        for (int i = left; i < right; i++) {
            if (list[i] < pivotElement) {
                swap (list, i, lastStoredIndex++);
            }
        }
        swap (list, lastStoredIndex, right);
        return lastStoredIndex;
    }

    private void swap (final int[] list, final int first, final int second) {
        final int temp = list[first];
        list[first] = list[second];
        list[second] = temp;
    }
}

#6

I will write this in english, but if you would like an explanation in norwegian, I can do that as well. I will not write you any code stub, since this is a homework, but try to imagine what you need to get done first: I guess the array a is unsorted, or atleast sorted but in reverse ways as shown in your text? a cannot be changed. k, of k length, is supposed to contain the k amount of lowest valued numbers in a. k must be sorted.

我会用英语写这个，但是如果你想用挪威语解释一下，我也可以。我不会给你写任何代码存根，因为这是一个作业，但试着想象一下你需要先做什么:我猜数组a是未排序的，或者至少是按照你的文本中显示的相反的方式排序的?不能改变。k, k的长度，应该包含a k中最小值的k值必须进行排序。

First and foremost, how do you solve problem number 1? What I would do (This is more inefficient in the beginning, but you wouldn't have to write as much code): Go through array a, starting by saving the first integer in index 0 in k. Let i++ work it's magic, and then call upon a method where you send in the entire array k, and the new integer. Make it check (with compareTo()-method) whether or not the new int is lower than the integer in every index in k, moving the other numbers one index ahead all the way (remember to check for null-values, orelse: NPE). Return this new array. This will allow you to save the k lowest numbers, sort them and not change a. I think it would solve your entire problem?

首先，如何解决问题1?我会怎么做(这是更低效率的一开始,但是你不需要编写大量代码):通过数组,通过保存第一个整数索引0开始在k。让我+ +工作的魔法,然后调用一个方法,你把整个数组k,和新的整数。让它检查(使用compareTo()-方法)，不管新int是否小于k中的每个索引中的整数，将其他的数字都移到前面的一个索引中(记住要检查null值，orelse: NPE)。返回这个新数组。这样你就可以节省k的最小值，对它们进行排序，而不是改变a。我想这会解决你的全部问题?