对未排序数组中的正整数进行排序。

This was given to me in a recent programming interview. I am given an unsorted array of integers with negative and positive values, and required to sort them but only for the positive values. I was wondering what some of your solutions might be without using Google.

这是在最近的一次编程面试中给我的。我得到了一个未排序的整数数组，这些整数具有负值和正的值，需要对它们进行排序，但只对正的值进行排序。我想知道您的一些解决方案可能不使用谷歌。

After getting home I found Arrays.sort() sorts the array in ascending order but I am not sure how to output to new array with only the positive values, as this was a requirement. I am able to print them by just printing if they are greater than -1, but how would I input them into new array without having to loop through the array and count the number of positive values to get the size of the new array, instantiate new array, then loop again to add them to new array.. This solution seems not optimal, is there a better way ?

回到家后，我找到了Arrays.sort()以升序对数组进行排序，但我不确定如何只以正值输出到新数组，因为这是一个要求。我能打印印刷如果大于1,但我怎么输入到新数组,而无需遍历积极的值的数组,数一数新数组的大小,实例化新数组,然后再次循环,将它们添加到新数组。这个解决方案似乎不是最优的，有更好的方法吗?

the output needs to be a new array with only positive values, that is sorted

输出需要是一个只有正值的新数组，该数组已被排序。

Below is what I have so far:

下面是我目前所拥有的:

  import java.util.Arrays;


    public class Test {

        public static void main(String[] args) {
            // TODO Auto-generated method stub      
            int[] unsorted = {
                -3, 95, -4, 20, 5, 6, 8
            };
            int[] sorted = unsorted;
            Arrays.sort(sorted);

            for (int s: sorted) {
                if (s > -1)
                    System.out.println(s);
            }
        }

    }

7 个解决方案

#1

You could try putting the data in a PriorityQueue, making sure to only deal with the positive values:

您可以尝试将数据放在优先队列中，确保只处理正值:

int[] unsorted = { -3, 95, -4, 20, 5, 6, 8 };

PriorityQueue<Integer> q = new PriorityQueue<>(unsorted.length);

for (int a : unsorted) {
    if (a > 0)
        q.add(a);
}

while (!q.isEmpty()) {
    System.out.println(q.poll());
}

This approach will be O(nlog(n)) where n is the number of positive integers in the array. Sorting the entire array, by contrast, will be O(nlog(n)) where n is the length of the entire array.

这个方法是O(nlog(n))，其中n是数组中正整数的个数。相比之下，对整个数组进行排序将是O(nlog(n))，其中n是整个数组的长度。

#2

What if you performed a binary search for 0 on your sorted array, and then only printed values from that point on? Arrays.binarySearch() returns the index that 0 WOULD be at if it doesn't find 0 in your array.

如果在排序的数组中执行二进制搜索0，然后只从该点上打印值，该怎么办?Arrays.binarySearch()返回的索引如果在数组中没有找到0，则为0。

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {    
        int[] unsorted = {
            -3, 95, -4, 20, 5, 6, 8
        };
        int[] sorted = unsorted;
        Arrays.sort(sorted);

        int breakingPoint = Arrays.binarySearch(sorted, 0);
        for (int i = breakingPoint; i < sorted.length; i++) {
            System.out.println(sorted[i]);
        }
    }

}

#3

You should make your own sorting algorithm. I would use a modified quicksort in an interview:

你应该自己做排序算法。我会在面试中使用一个修改过的快速排序:

1-pick 0 to be the pivot for the first recursive call and put all numbers that are equal or bigger than 0 on the right array

1-选择0作为第一个递归调用的主元，并将所有大于0的数字放在右边的数组中。

2-Only call quicksort on the right array for the first recursive call,for the other recursive calls,use a random pivot.

对于第一个递归调用，只调用右边数组中的快速排序，对于其他递归调用，使用一个随机的主元。

3- When concatenating,remove the first 0 you find.

3-连接时，删除第一个0。

Fast(nlogN),and you can do it even in the same array,or return a new one.

快速(nlogN)，你甚至可以在相同的数组中完成，或者返回一个新的数组。

#4

In Java, the Collection.sort must be stable, so if you have use a comparator that says that all negative numbers are equal, but for positive numbers does what you'd expect, you'd have what you need.

在Java中,集合。排序必须是稳定的，所以如果你使用一个比较器，它说所有的负数都是相等的，但是对于正数，你会得到你所期望的，你会得到你需要的。

#5

Creating a list just for the dynamic aspect would mean potentially resizing the array multiple times during the removal process.

为动态方面创建一个列表意味着在删除过程中可能多次调整数组的大小。

I elected instead to use Arrays.copyOf to resize the array after I knew how big it needed to be.

我选择使用数组。在我知道它需要多大的时候，就可以调整数组的大小。

The first thing I did was filter out the negatives:

我做的第一件事就是过滤掉底片:

int[] unsorted = {
    -3, 95, -4, 20, 5, 6, 8
};

int[] positives = new int[unsorted.length]; //It can only be as big as unsorted.

int i = 0, j = 0;

for (; i < unsorted.length; i++) {
    if (unsorted[i] >= 0)
        positives[j++] = unsorted[i];
}

Then, I resize the array:

然后调整数组的大小:

positives = Arrays.copyOf(positives, j);

Finally, I sort it:

最后,我:

Arrays.sort(positives);

Here is an IDEOne.com demo

这是一个IDEOne.com的演示。

#6

simple separate the positive numbers - it needs one copy

简单的把正数分开——它需要一个副本。

List<Integer> positives = new ArrayList<Integer>();
for (Integer number: unsorted) {
    if (number > 0) {
        positives.add(number);
    }
}

and then sort them.

然后排序。

Collections.sort(positives);

#7

Iterate the array
数组遍历
For each positive value, store the position and value into two arrays
对于每个正值，将位置和值存储到两个数组中。
Sort the value array
排序数组的值

#1