如何优化关于如何计算它们之间没有值的数组元素数量的查询 [英] how to optimize query on how to count number of array elements that don't have values between them

问题描述

我想编写一个方法，当提供一个整数数组时，它会执行以下操作.对于每对数组元素，它将组合它们并将它们放入内部类对象的列表中.然后它将比较数组中的每个元素并检查它是否适合每对值.(即我有一个数组 0, 2, 4 它会生成例如对 (0,4) 然后它会检查值 2 确实在 0 和 4 之间，所以对于对 (4,0).当对 (0, 2) 被评估它不会找到任何东西，因此计数器会增加(对 (2, 0) 也是如此).我构建了以下代码来评估确实适合成对的值的数量，我希望然后通过从对的总数中提取它来获得符合我需要的对的总数.现在我想优化这个查询(如果我有包含数千个成员的非常大的数组和非常大的或负整数，例如 1,000,000,000 或 - 2,000,000,000).请告诉我该怎么做.主要请关注优化问题，谢谢.

I want to write a method that when supplied an array of ints will do the following. For each pair of array elements it will combine them and put them into a list of an inner class objects. Then it will compare each element in the array and check if it will fit between each pair values. (i.e. I have an array 0, 2, 4 it will make for example pair (0,4) and then it will check that value 2 is indeed between 0 and 4 and so for pair (4,0). When pair (0, 2) is evaluated it won't find anything and therefore counter will increase (and so for pair (2, 0)). I have constructed the following code to evaluate number of values that indeed will fit in pairs and I hoped then to get the total number of pairs that match my need by extracting it from the total number of pairs. Now I want to optimize this query (in case I have very big arrays with thousands of members and very big or negative integers e.g. 1,000,000,000 or - 2,000,000,000). Please let me know how to do that. Mainly please focus on optimization issues thank you.

import java.util.*;
import java.util.Map;
import java.lang.*;

public class Prac1 {
    public int count(int[] A){
        int k = 0;
        class PTemp{        
            int first = 0;
            int second = 0;
            public PTemp(int first, int second){
                this.first = first;
                this.second = second;               
            }   
        }
        List<PTemp> r = new ArrayList<PTemp>();
        int z = 0;
        for (int i = 0; i < A.length; i++) {
              for (int j = i+1; j < A.length; j++) {
                  r.add(new PTemp(A[i], A[j]));
                  r.add(new PTemp(A[j], A[i]));
                  z = z + 2;
                  System.out.println("["+A[i] +","+A[j]+"]");
                  System.out.println("["+A[j] +","+A[i]+"]");
              }
            }
        Iterator<PTemp> ir = r.iterator();
        while (ir.hasNext()){
            PTemp p = ir.next();
            label1:
            for (int i = 0; i < A.length-1; i++){

                if (((p.first < A[i]) && (A[i] < p.second)) || ((p.first > A[i]) && (A[i] > p.second))){
                    k = k + 1;
                    break label1;
                }
            }           
        }
        System.out.println(z);
        k = z - k;
        return k;       
    }
    public int c(int[] A) {
         int z = (A.length - 1) * 2;
         return z;
        }
    public static void main(String[] args){
        int[] A = {0, 2, 2, 6, 5, 5};
        Prac1 pr = new Prac1();
        System.out.println(pr.count(A));
        System.out.println(pr.c(A));
    }
}

推荐答案

不失一般性，我们可以考虑对数组进行排序.假设数组中的所有数字都是不同的，中间没有元素的对是由邻居组成的对.有 (array.length - 1) * 2 个这样的对，即你可以简单地做:

Without loss of generality, we can consider the array to be sorted. Assuming all numbers in the array are distinct, the pairs without elements in between are the pairs formed by neighbours. There are (array.length - 1) * 2 such pairs, i.e. you could simply do:

public int count(int[] A) {
   return (A.length - 1) * 2;
}

如果数组可能包含重复项，您应该指定如何计算它们.

If the array may contain duplicates, you should specify how they are to be counted.

这篇关于如何优化关于如何计算它们之间没有值的数组元素数量的查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！