大小为k的数组(大小为n)的子集的数量，最大元素与最小元素在最大x上的差异

I came across this question during a test. Given an array of size n find number of subsets of size k having difference between maximum and minimum element at most x.

我在一次考试中遇到了这个问题。给定一个大小为n的数组，找出大小为k的子集的数量，最大元素和最小元素在最大x上的差异。

Constraints 1<=a[i],n,k,x<=10^6
Example:n=5 k=3 x=5 a={1,2,3,4,5}
output: 10

My Approach So Far: I first sorted the array and considered the greatest element . Now using linear search I found the smallest element whose such that difference is less than or equal to x.

我的方法是:首先对数组进行排序，然后考虑最大的元素。现在我用线性搜索找到了最小的元素它的差小于或等于x。

Now if I take that greatest element and selected any k-1 elements between them .Selection process was (index of greatest - index of smallest)C(k-1) and I summed up these.

现在，如果我取这个最伟大的元素，并在它们之间选取任意k-1元素。选择过程是(最小值的索引)C(k-1)，我总结一下。

Complexity is coming around O(nnk). I wasn't stuck but my solution couldn't pass the test cases.

复杂性正围绕着O(nnk)而来。我没有被卡住，但是我的解决方案不能通过测试用例。

2 个解决方案

#1

I think you're on the right track. As I understand it, this is what you have so far:

我觉得你走对了。据我所知，这是你们目前所拥有的:

Sort the array.
- You don't say how you're doing this, but you can do it in O(n) time using a radix sort, so I'll assume O(n) time.
- 你不会说你是怎么做的，但是你可以在O(n)时间用基数排序，所以我假设O(n)时间。
数组进行排序。你不会说你是怎么做的，但是你可以在O(n)时间用基数排序，所以我假设O(n)时间。
For each element:
- Count how many other elements are between E − x and E (where E is the value of this element). Call the result m.
  - You're doing this in worst-case O(n) time by using a linear search.
  - 用线性搜索在最坏情况O(n)时间内做这个。
- 数有多少其他元素之间的E−x和E(E是该元素的值)。调用结果m，在最坏情况下O(n)时间内，通过线性搜索。
- Compute _mC_k−1.
  - You don't say how you're doing this, but you can precompute this for all possible m in O(n) time and then just use a constant-time lookup, so I'll assume that's what you're doing.
  - 你不会说你是怎么做的，但是你可以在O(n)时间内对所有可能的m进行预先计算，然后使用常量时间查找，所以我假设这就是你要做的。
- 计算mCk−1。你不会说你是怎么做的，但是你可以在O(n)时间内对所有可能的m进行预先计算，然后使用常量时间查找，所以我假设这就是你要做的。
为每个元素:数数有多少其他元素之间的E−x和E(E是该元素的值)。调用结果m，在最坏情况下O(n)时间内，通过线性搜索。计算mCk−1。你不会说你是怎么做的，但是你可以在O(n)时间内对所有可能的m进行预先计算，然后使用常量时间查找，所以我假设这就是你要做的。

This approach gives the correct result, and requires worst-case O(n²) time. (You mention that you were getting O(n²k) time; but I don't see any reason for that.)

这种方法给出了正确的结果，并且需要最坏的O(n2)时间。(你说你得到了O(n2k)的时间;但我看不出有什么原因。

The major optimization that you seem to be missing is that instead of restarting your linear search for each element, you can resume your linear search from where the previous element's linear search left off. That way, all of your linear searches put together will add up to linear time, since they amount to just a single pass over the array. (In other words, your linear searches will have amortized constant time.)

似乎你失踪的主要优化,而不是重新启动你的线性搜索每个元素,你可以恢复你的线性搜索从前面元素的线性搜索。这样的话,你所有的线性搜索放在一起会增加线性时间,因为他们只是一个经过数组。(换句话说，线性搜索会得到平摊常数时间)

This gives us an algorithm in O(n) time:

这给了我们一个O(n)时间的算法:

sort a
precompute nCr(m, k - 1) for all m in (0 .. n-1)
set total_num_subsets := 0
set min_element_index := 0
for max_element_index in 0 .. n-1 do:
    while a[min_element_index] + x < a[max_element_index] do:
        set min_element_index := min_element_index + 1
    set num_eligible_elements := max_element_index - min_element_index
    set num_subsets := nCr(num_eligible_elements, k - 1)
    set total_num_subsets := total_num_subsets + num_subsets

(There are some additional minor optimizations we can do — for example, we can start the max_element_index iteration at k rather than 0, and we can use memoization rather than precomputation to avoid computing _mC_k−1 for larger values of m than we actually end up needing — but they don't change the algorithmic complexity.)

(我们可以做一些额外的小优化——比如,我们可以开始max_element_index迭代在k,而不是0,我们可以使用记忆而不是预先计算来避免计算mCk−1 m的值比我们实际上最终需要——但他们不改变算法复杂度)。

#2

I hope it will help you.

我希望它能对你有所帮助。

First to get subset of length k recursively .
首先得到长度k的子集递归。

If current length is equal to k

如果电流长度等于k

2.1 then store in auxiliary array a with length of k

2.1然后存储在辅助阵列a中，长度为k。

2.2 Sort it in k*log(k)

2.2用k*log(k)排序

2.3 get absolute difference between first and last element.(As first is minimum and last is maximum)

2.3求第一个元素和最后一个元素的绝对值。(因为第一是最小，最后是最大值)

2.4 check difference is less than equal to 4 then count++;

2.4检验差小于4，则计数+;

 public class AllSubSetOfSizeK 
   {

   static int count=0; 
  public void get_SubSet(int[] A, int k, int start_index, int curr_Len,  boolean[] used)


  {

int a[]=new int[k];
int l=0;

if (curr_Len == k) {
    for (int i = 0; i < A.length; i++) {
        if (used[i] == true) {
            a[l++]=A[i];
        }
    }
    Arrays.sort(a);//To Sort the Array of k length
    if(Math.abs(a[0]-a[k-1])<=4);
        count++;
    return;
}
if (start_index == A.length) {
    return;
}

used[start_index] = true;
get_SubSet(A, k, start_index + 1, curr_Len + 1, used);

used[start_index] = false;
get_SubSet(A, k, start_index + 1, curr_Len, used);

}
 public static void main(String[] args) 
  {
    int A[] = { 1,2,3,4,5};
     boolean[] B = new boolean[A.length];
     AllSubSetOfSizeK obj = new AllSubSetOfSizeK();
    obj.get_SubSet(A, 3, 0, 0, B);
    System.out.println(count);

  }

}

#1