使用 TreeSet 计算反转 Java

Question

我正在使用 treeSet 解决计数倒置问题。我正在使用以下方法，该方法使用 gnu_pbds 在 O(logn) 时间内工作。

算法

在Ordered_Set中插入数组的第一个元素。
对于 arr[] 中的所有剩余元素，执行以下操作：

在Ordered_Set中插入当前元素。
使用函数 order_of_key(arr[i]+1).

Ordered_Set

Ordered_Set 和 order_of_key(current_element + 1) 的大小之差将给出当前元素的反转计数。

You can read more about this algorithm here.

For order_of_key method I'm using TreeSet's headset(k) method for calculation.

这是我的代码。

public class Solution {
    
    static int order_of_key(TreeSet<Integer> s, int k)
    {
                return s.headSet(k,true).size();
    }
    public int solve(ArrayList<Integer> a) {
    
        TreeSet<Integer> s = new TreeSet<>();
        s.add(a.get(0) );
        int invcount = 0;
        for(int i=1;i<a.size();i++)
        {
            s.add(a.get(i) );
            int key = order_of_key(s, a.get(i)+1);
            // if(i+1 == a.size() ) key--;
            invcount+= s.size() - key;
            
           // System.out.println(s+" "+(a.get(i)+1)+" "+ key+" "+invcount);
                  
        }
        return invcount;
        
    }
}

相应的 C++ 代码

// Ordered set in GNU C++ based 
// approach for inversion count 
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std; 

// Ordered Set Tree 
typedef tree<int, null_type, less_equal<int>, 
            rb_tree_tag, 
            tree_order_statistics_node_update> 
    ordered_set; 

// Returns inversion count in 
// arr[0..n-1] 


void print(ordered_set s,int n){
  
 for(int i=0;i<n;i++)
 {
  // printf("%d ",s[i]);// <<endl; 
 cout << *(s.find_by_order(i))  
         << " ";
 }
  //cout<<endl;
}

int getInvCount(int arr[], int n) 
{ 
    int key; 
    // Intialise the ordered_set 
    ordered_set set1; 

    // Insert the first 
    // element in set 
    set1.insert(arr[0]); 

    // Intialise inversion 
    // count to zero 
    int invcount = 0; 

    // Finding the inversion 
    // count for current element 
    for (int i = 1; i < n; i++) { 
        set1.insert(arr[i]); 
        // Number of elements strictly 
        // less than arr[i]+1 
        key = set1.order_of_key(arr[i] + 1); 

        // Difference between set size 
        // and key will give the 
        // inversion count 
        invcount += set1.size() - key; 
        print(set1,n);
      cout<<arr[i]+1<<" ";
      cout<<key<<" ";
      
        cout<<" "<<invcount<<endl;
        
    } 
    return invcount; 
} 

// Driver's Code 
int main() 
{ 
    int arr[] = { 32, 35, 43, 1, 38, 39, 42 }; 
    int n = sizeof(arr) / sizeof(int); 
     cout<<n<<endl;
    // Function call to count 
    // inversion 
    cout << getInvCount(arr, n); 
    return 0; 
}

观察

我的解决方案适用于所有测试用例，但对于一些微不足道的测试用例，它 returns 1- inversion count。如果我将 order_of_key 的工作方式更改为以下内容，它会破坏其他一些测试用例。

int order_of_key(TreeSet<Integer> s, int k)
    {
            if(s.contains(k))
                return s.headSet(k).size();
            else
                return s.headSet(k,true).size();
    }

但 gnu_pbds 一直有效。

请帮助我使用 TreeSet 修复此代码。另外，如果我遗漏了关于 pbds order_of_key 方法的其他一些要点，请告诉我。

Answer 1

order_of_key 函数 returns 小于提供键的元素数。在您的 C++ 代码中，您将元素添加到集合中，然后调用 order_of_key 元素加一，以便包含您刚添加的元素。

在 Java 代码中保留这种安排，忠实地使用 Java TreeSet 实现类似 order_of_key 的方法是调用

return s.headSet(k, false).size();

或者干脆

return s.headSet(k).size();

因为其中任何一个 returns 包含元素的头集的大小严格小于 k。无需先进行包含检查。当我运行使用你的 C++ 代码中的输入数组时，我得到了相同的中间结果和最终结果的反转次数：6.

请注意 Java 的 TreeSet 还包括创建尾集的能力，即大于提供的元素的元素。结果证明（在我看来）这是一种计算反转次数的更简单的方法。在添加一个元素之前，大于当前元素的tail-set的大小就是相对于这个元素的反转次数。因为我们希望尾集严格大于当前元素，所以我们使用 tailSet(k, false)。然后我们可以对输入列表中的每个元素执行此操作：

int inversions(List<Integer> a) {
    var s = new TreeSet<Integer>();
    int invcount = 0;
    for (int k : a) {
        invcount += s.tailSet(k, false).size();
        s.add(k);
    }
    return invcount;
}

inversions(List.of(32, 35, 43, 1, 38, 39, 42)) // result is 6

更新 2020-06-24

以上代码仅适用于具有唯一值的输入。如果输入有重复值，则不起作用。我注意到在 C++ 代码中，使用 less_equal<int> 比较函数的树会保留重复项，而使用 less<int> 会压缩重复项。

保持重复很重要的原因是每个元素——即使它是重复的——都可以算作一个反转。因此，[2, 2, 1] 的输入被认为有两个反转。 Java TreeSet 压缩了重复项，因此我们必须做一些额外的工作来保留它们。

允许“重复”int 值的一种方法是以某种方式使它们唯一。这可以通过创建一个新对象来完成，该对象包含与始终递增的计数器配对的 int 值。重复值是唯一的，因为它们将具有不同的计数器值。这里有一个 class 可以做到这一点：

static class UniqInt implements Comparable<UniqInt> {
    static int count = 0;
    final int value;
    final int uniq;
    UniqInt(int value) { this.value = value; uniq = count++; }
    public int compareTo(UniqInt other) {
        int c = Integer.compare(this.value, other.value);
        return c != 0 ? c : Integer.compare(this.uniq, other.uniq);
    }
}

请注意，此处的 compareTo 方法比较值和“uniq”计数器值，因此创建多个 UniqInt 实例将彼此不同并且将完全排序。一旦我们有了这个 class，我们基本上做同样的事情，除了我们在 TreeSet 中跟踪 UniqInt 而不是 Integer 对象。

int inversions1(List<Integer> a) {
    var s = new TreeSet<UniqInt>();
    int invcount = 0;
    for (int k : a) {
        var u = new UniqInt(k);
        invcount += s.tailSet(u, false).size();
        s.add(u);
    }
    return invcount;
}

对于评论中提供的输入（包括重复值），

84, 2, 37, 3, 67, 82, 19, 97, 91, 63, 27, 6, 13, 90, 63, 89, 100, 60, 47, 96, 54, 26, 64, 50, 71, 16, 6, 40, 84, 93, 67, 85, 16, 22, 60

这给出了预期结果 290。

然而，这有点脆弱。请注意，创建一个具有相同值的新 UniqInt 总是创建一个大于任何现有实例的实例，因为计数器总是递增的。（直到您创建了其中的 2^31 个。）创建新实例时，其尾部集将永远不会包含 TreeSet 中已有的任何重复值。这对于这个小例子来说可能是合理的，但如果这是一个更大系统的一部分，我会更仔细地考虑如何相对于某个值获得正确的头组或尾组，而不必依赖大多数最近创建的 UniqInt 比以前的都大。

使用 TreeSet 计算反转 Java

Counting Inversions using TreeSet Java

java

c++

g++

treeset

算法

这是我的代码。

相应的 C++ 代码

观察