gpt4 book ai didi

java - 如何将 'Double for loop(O(n^2))' 变成 'Single for loop(O(n))' ?

转载 作者:行者123 更新时间:2023-11-29 09:43:09 25 4
gpt4 key购买 nike

<分区>

我正在研究算法,我正在努力使它变得更加高效和清洁。

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

下面是我的代码。

// 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 循环(而不是两个 for 循环。)你认为这可能吗?

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com