时间戳

首页 > 解决方案 > 在 Java 中忽略或删除数据集中某些元素的最佳数据结构是什么？

java - 在 Java 中忽略或删除数据集中某些元素的最佳数据结构是什么？

问题描述

我有一组对象，我想检查每个元素与以前的元素。由于时间复杂性，我每次if(thisElement % previousElement == 0)都想忽略previousElement以防止再次检查。DataSet如果条件为真，我如何减小大小？标记并移动previousElement到第一个DataSet或完全删除它会更好吗？我使用ArrayList了对象，但我无法移动或删除它。我也使用过Iterator，但它应该在另一个循环中有一个循环，而且很复杂。我怎样才能在最佳时间实现这个算法？我想在 O(1) 中移动或删除 previousElement。这是我的代码：

public static int count_max(ArrayList<Node> nodes){
        
        int max = Integer.MIN_VALUE;
        int counter = 0;
        System.err.println("nodes: "+nodes);
        for(Node n : nodes){
        
            int index = nodes.indexOf(n);
            for(int i = index - 1 ; i >= 0 && nodes.get(i).mark == 0 ; i--){
            
                counter++;
                if(n.number % nodes.get(i).number == 0){
                    
                    n.pred = i;
                    nodes.get(i).mark = 1;
                    n.count = nodes.get(i).count + 1;
                    if(n.count > max)
                        max = n.count;
                    //nodes.remove(i);

                    break;
                }
            
            }

        }
        return max;
    }

问题是找到给定的可除数的最大计数，例如考虑给出 [3, 4, 6, 8 ,10, 18,21,24]。答案是 3 因为 [3 , 6 , 18 ] 或 [4 , 8 , 24] 所有成员都应该是可分的 你有什么解决方案在 o(nlogn) 中找到这个或更大一点。我不想在 o (n^2)

标签： javaarraylistdata-structuresiterator

解决方案

如果您提供了您实施的逻辑可能会更好，但是根据您的解释，我的理解是，如果前一个元素将当前元素与列表完全分开 ，您希望删除它。如果是这样，下面提到的方法很容易遵循

MainClass.class

    public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();

    list.add(2);
    list.add(4);
    list.add(8);
    list.add(10);
    list.add(9);
    int i = 1;

    System.out.println("Size of List: " + list.size());
    while (i < list.size()) {
        System.out.println("i : " + i);
        System.out.println("Values : " + list.get(i) + ", " + list.get(i - 1));
        if (list.get(i) % list.get(i - 1) == 0) {
            System.out.println("Removing: " + list.get(i - 1));
            list.remove(i - 1);
            i = 1;
        } else {
            i = i + 1;
        }
    }
    System.out.println("After removing elements(if any), size is: " + list.size());
    for (int val : list) {
        System.out.print(val + " ");
    }
}

这段代码所做的是，它从i=1开始，并不断检查第 (i-1) 个值是否除以第 i 个值。如果(i-1)th除以第 i 个值，则i设置为“1”，因为我们需要从头开始并保持条件，即，第 (i-1) 个值不应该除以第 i 个值。你可以猜到，如果任何值不能被它的前一个元素整除，那么我们只需递增i直到它小于 List 的大小。

注意：我假设您希望在整个列表 中保持上述条件

， 我希望这可以以某种方式帮助您解决您的问题。如果有人觉得需要，可以编辑这篇文章。

推荐阅读