java - 如何将“Double for loop(O(n ^ 2))”变成“Single for loop(O(n))”？

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。
                        
                        2年前关闭。
                                                                                            
                
        
我正在研究算法，并且正在尝试使其变得更高效，更简洁。

这是一种算法，该算法查找不重复的值并返回其中的第一个值。

这是下面的代码。

// example input of array.
int[] A = [2, 5, 1, 5, 1, 3, 9, 2];

// check pairs. And make them -1
// from 0 index to last index.
for(int i = 0 ; i < A.length ; i++){
    // from the next index to the last index ( the rest indices ).
    for(int j=i+1; j < A.length ; j++){
        // if ith value and jth value are euqal and never checked make them -1 so that you can mark they have been visited.
        if(A[i]==A[j] && A[i]>0){
            A[i]=-1; A[j]=-1;
        }
    }
}

// find the first number among the left positive values.
for(int i = 0 ; i < A.length ; i++){
    if(A[i]>0) return A[i];
}
// if there is no positive value, return 0;
return 0;

如您所见，这是O（n ^ 2）。我正在尝试使其更快或更干净。我想我可以使这个O（n），这意味着仅使用一个for循环（而不是double for循环。）您认为有可能吗？

最佳答案

如@ gabi13的回答所述，可能最简单，最有效的方法是使用O（nlogn）排序算法，然后遍历数组以搜索不等于下一个（或上一个）的第一个元素。

但是，我想进一步澄清一下，因为您似乎在问题中混淆了复杂性概念。

将两个循环简化为一个循环不会将O（n²）转换为O（n），除非它们是嵌套的（但是您需要一种方法来丢弃最后一个循环，而不是嵌套的循环）。

您的第一个循环是导致O（n²）的循环，因为它有2个嵌套的循环遍历数组。即使删除最后一个循环，您的代码也将保持O（n²）。

尽管您的方法无法转化为O（n）（有关替代方法O（nlogn），请参见@ gabe13的答案），但可以优化您的实现。

首先，如果只需要关注正值，则在A [i]
另外，如果您只想要第一个非重复的正数元素，那么如果您找不到重复项，则仅在A [i]> 0的情况下检查第一个嵌套循环就足够了（即，嵌套循环在没有findind的情况下结束了）一双）。在这种情况下，您已经有了解决方案。

关于java - 如何将“Double for loop(O(n ^ 2))”变成“Single for loop(O(n))”？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44198478/