无需蛮力方法即可避免嵌套循环的最佳算法

Question

我想让这个方法运行尽可能快。

int[] p = new int[] {1,4,4,5,1,3,6};
int[] q = new int[] {2,1,3,1,6,4,3};
int k =4.
void nestLoop(){
 for(int i = 0; i < q.length; i++){
     for(int j = 0; j < p.length; j++){
       //code continues 
       // inside here...
       //This approach 
        // takes a longer 
         //time to finish 
         // executing. I need a better algorithm

      }


  }
}

更清楚；在q[0]，p=1，因为1小于q[0]，所以选1，p[4]也小，所以选1；因此当它是 q[0] 时的答案是 1 和 1：但是因为 1 和 1 是两个整数，它们不等于 k = 4，那么 return 0。如果答案是 1、1， 1,1 那么数字是 4 等于 k。 [1,1,1,1] 将被 return 编辑。其他q等同理

Answer 1

如果p中different个元素的个数相对于total个元素个数比较少，下面可能有效。但是，如果有很多不同的元素，甚至所有元素都不同，那么它会慢很多。

创建一个 Map 映射元素到它们的索引，例如[1,4,4,5,1,3,6] 会变成 {1: [0,4], 4: [1,2], 5: [3], 3: [5], 6: [6]}
从该映射中，获取小于 q
将它们放入堆或优先队列中，按该元素的下一个未使用索引排序
从堆中弹出列表，获取第一个索引，然后将它们放回堆中以获取下一个索引，直到获得 k 个索引

如果有很多重复的元素（并且只有这样），这可能会稍微降低复杂性。对于 p 中的 P 个元素，d 个不同的元素，q 中的 Q 个元素，以及 k，这应该具有 O(P + Q*(d+k*log(d)))（P 用于创建映射，d 用于选择列表，k 堆操作，log(d) 用于所有 Q 查询）。

Answer 2

这是一个使用 Java 流的解决方案：

package javaapplication3;
import java.util.Arrays;
import java.util.stream.*;

public class JavaApplication3 {
    public static void main(String[] args) {

        int[] p = new int[] {1,4,4,5,1,3,6};
        int[] q = new int[] {2,1,3,1,6,4,3};
        int[][] results = new int[q.length][]; // Array of arrays to store results
        int k =4;
        
        // For each element q[i], execute in parallel
        IntStream.range(0, q.length).parallel().forEach(i -> {
            final int qi = q[i];
            // Get first k elements of p <= q[i]
            results[i] = Arrays.stream(p).filter(v -> v <= qi).limit(k).toArray();            
        });
        
        for(int i=0; i<q.length; i++) {
            int[] result = results[i];
            System.out.print("Values less or equal than " + q[i] + ": {");
            for (int v : result)
                System.out.print(" " + v);
            System.out.println(" }");
        }

    }    
}

输出：

Values less or equal than 2: { 1 1 }
Values less or equal than 1: { 1 1 }
Values less or equal than 3: { 1 1 3 }
Values less or equal than 1: { 1 1 }
Values less or equal than 6: { 1 4 4 5 }
Values less or equal than 4: { 1 4 4 1 }
Values less or equal than 3: { 1 1 3 }

注意：您可以选择对 p 进行排序，如果 p 较大且 k 较小，这将提高性能。

Answer 3

如果我理解正确，你返回的是 k 或 0，对吗？

那么方法是这样的：

int[] p = new int[] {1,4,4,5,1,3,6};
int[] q = new int[] {2,1,3,1,6,4,3};
int k =4.

void notNested()
{
    TreeSet<Integer> ts = new TreeSet<Integer>();
    // Find the kth smallest number in the array.
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    for (int p1 : p)
    {
        if (pq.size() < k)
        {
            pq.add(p1);
        } else if (pq.peek() > p1)
        {
            pq.poll();
            pq.add(p1);
        }
    }

    int ksm = pq.poll();
    // For each q, compare against kth smallest only.
    for (int q1 : q)
    {
        if (q1 >= ksm)
        {
            results.add(k);
        }
        else
        {
            results.add(0);
        }
    }
}

无需蛮力方法即可避免嵌套循环的最佳算法

Best Algorithm to avoid nested loops without Brute Force approach

java

algorithm

brute-force

nested-loops