如何找出任何两个元素总和> k的子数组？

Last weekend I was asked this question in an interview. There is an array of positive numbers. From this array , you need to find out the subset. From this subset, you should be able to pick up any two numbers and their sum would always be greater than k. k is an user inputted value.

上周末我在接受采访时被问到这个问题。有一系列正数。从这个数组中,您需要找出子集。从这个子集中,您应该能够获取任意两个数字,它们的总和将始终大于k。 k是用户输入的值。

I was able to solve this question in two passes. In the first pass, I will pick up all the items greater than k and put them in the sub array. While doing so, I will find out the minimum value from this subset.

我能够在两次通过中解决这个问题。在第一遍中,我将拾取大于k的所有项并将它们放在子数组中。在这样做的同时,我将从该子集中找出最小值。

In the next pass,I will sort the array in descending order. After that I will keep adding numbers to the subset by summing them up with the minimum number in the subset.

在下一个传递中,我将按降序对数组进行排序。之后,我将通过将它们与子集中的最小数字相加来继续向子集添加数字。

The solution mentions above solves the problem. However the time complexity would be O(n + nlogn). However the interviewer wanted it to be O(n). Needless to say I was not able to do that. Please help me with the algorithm. I did try to search the internet. However I could not find anything with o(n) time complexity.

上面提到的解决方案解决了这个问题。然而,时间复杂度将是O(n + nlogn)。然而面试官希望它是O(n)。不用说我无法做到这一点。请帮我解决这个问题。我确实试图搜索互联网。但是我找不到任何具有o(n)时间复杂度的东西。

2 个解决方案

#1

Add all the numbers greater than k/2 to the subset (keep track of the minimum).

将大于k / 2的所有数字添加到子集中(跟踪最小值)。

Go through the array again and add any number greater than k-minimum of subset to the subset. Stop after we added 1.

再次遍历数组并将任何大于k最小子集的数字添加到子集中。我们加1后停止。

If this is part of the requirements, you can look for the biggest one.

如果这是要求的一部分,您可以寻找最大的要求。

This runs in O(n).

这在O(n)中运行。

The reasoning here is as follows:

这里的推理如下:

Any 2 elements > k/2 will add up to more than k.

任何2个元素> k / 2将加起来超过k。

If one element is <= k/2, the other element will need to be > k/2 to add up to at least k, so there can't be more than one element <= k/2 (since if there were 2, those 2 won't add up to more than k).

如果一个元素<= k / 2,则另一个元素需要> k / 2才能加起来至少为k,所以不能有多个元素<= k / 2(因为如果有2个元素) ,那些2不会加起来超过k)。

An example of this is k = 10, array = [3,4,8,9,10], with the output being [3,8,9,10] or [4,8,9,10]. 8,9,10 will get added in the first step, then we'll add 3 or 4 in the second step.

一个例子是k = 10,array = [3,4,8,9,10],输出为[3,8,9,10]或[4,8,9,10]。 8,9,10将在第一步中添加,然后我们将在第二步中添加3或4。

Technical note: "Subset" implies unique elements. We can use a hash table to get expected (but not guaranteed) O(n) complexity. If it's instead a "subsequence" (not unique elements), we can just add them to an array or linked-list for O(n) complexity.

技术说明:“子集”意味着独特的元素。我们可以使用哈希表来获得预期(但不保证)的O(n)复杂度。如果它是“子序列”(不是唯一元素),我们可以将它们添加到数组或链表中以获得O(n)复杂度。

#2

Yes, it is possible to solve it with complexity O(n). With a single loop on the array, take only numbers that are greater than k/2. A simple algorithm would look like this:

是的,可以用复杂度O(n)来解决它。使用阵列上的单个循环,仅采用大于k / 2的数字。一个简单的算法如下所示:

for(int i=0; i<n; i++){
    if(arr[i] > k/2.0){
         add arr[i] to the subset
    }
}

#1

Add all the numbers greater than k/2 to the subset (keep track of the minimum).