我正在研究算法，我正在努力使它更有效和更干净。
这是一种算法，它查找不重复的值并返回其中的第一个值。
这是我下面的代码。
// 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 循环(而不是双倍循环)。你认为这可能吗？
如@gabi13的回答所述，可能最简单和最有效的方法是使用 O(nlogn) 排序算法，然后遍历数组搜索第一个不等于下一个(或上一个)的元素。
但是，我想进一步澄清一下，因为您似乎混淆了问题中的复杂性概念。
将两个循环减少为一个不会将 O(n²) 转换为 O(n)，除非它们是嵌套的(但您要求一种方法来丢弃最后一个循环，而不是嵌套循环)。
您的第一个循环是导致 O(n²) 的循环，因为它有 2 个嵌套循环遍历数组。即使删除最后一个循环，代码仍将保持 O(n²)。
尽管你的方法不能变成O(n)(参见@gabe13对替代方法O(nlogn)的回答)，但你的实现可以得到优化。
首先，如果你只需要关注正值，你不需要检查A[i]<=0的对。将该条件移到嵌套循环之外将提高效率。
此外，如果你只想要第一个正非重复元素，如果你没有找到重复(即嵌套循环结束而没有找到一对)，则只检查第一个嵌套循环就足够了，只针对 A[i]>0)。在这种情况下，您已经有了解决方案。
是否要返回第一个不重复的元素或任何元素？因为如果你不必是第一个，你可以在O(nLGn)中做到这一点。使用一些需要对数时间的方法对数组进行排序，例如 mergesort，然后通过查找一个位置与下一个/上一个位置不同来遍历它
因此，据我了解，如果没有返回 0，您想返回第一个既不是 0 也不是在下一个位置重复的值？
怎么样：
for( int i=0; i<A.length-1;i++)
{
if( A[i]>0 && A[i]!=A[i+1] ) return A[i];
}
return 0;
当然，如果你还需要修改数组，因为你将继续使用它，你将需要进一步的逻辑。
如果你使用的是Java，你可以使用HashMap。
使用HashMap在列表中查找未重复数字的代码：
public class NonDuplicateNumber {
public static void main(String[] args) {
int[] arr = {1,3,2,5,7,6,9,8,10,1,3,2,5,7,6,9,8,10,4};
Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
for(int i=0;i<arr.length;i++) {
if(countMap.containsKey(arr[i])) {
int count = countMap.get(arr[i]);
count++;
countMap.put(arr[i], count);
} else {
countMap.put(arr[i], 1);
}
}
Set<Integer> keySet = countMap.keySet();
for(Integer key : keySet) {
int count = countMap.get(key);
if(count == 1) {
System.out.println("Non duplicate number: "+key);
}
}
}
}
您可以使用整数排序的想法。它是三个循环，但它们不是嵌套的。它可以处理负数。时间复杂度O(n+m)其中n是数组的长度，m是数组中最大值和最小值之间的差值。
下面是一个工作 java 示例：
public class findDup {
public static void main(String[] args) {
int arr[] = { -4, -6, -4, 8, 9, 8, 9, 10, -3 };
printNonDups(arr);
}
public static void printNonDups(int arr[]) {
// Find max and min.
int max=arr[0];
int min=arr[0];
// Find max and min.
// O(arr.length)
for(int i=0; i<arr.length; i++) {
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
min=arr[i];
}
int tmp[] = new int[max-min+1];
// Count the number of occurrences of each number.
// O(arr.length)
for(int i=0; i<arr.length; i++)
tmp[arr[i]-min]++;
// Print all unique values
// O(max-min)
for(int i=0; i<tmp.length; i++)
if(tmp[i]==1) {
System.out.println(i+min);
// break; // Uncomment to stop after first non-duplicate
}
}
}
它是三个循环，但它们不是嵌套的。它可以处理负数。时间复杂度O(n+m)其中n是数组的长度，m是数组中最大值和最小值之间的差值。