我参加了一次面试,其中有以下问题:
在少于 O(n) 的时间内从已排序的数组中查找唯一数字。
Ex: 1 1 1 5 5 5 9 10 10
Output: 1 5 9 10
我给出的解决方案时间复杂度为O(n)。编辑:已排序数组大小约为200亿,唯一数字约为1000个。
我参加了一次面试,其中有以下问题:
在少于 O(n) 的时间内从已排序的数组中查找唯一数字。
Ex: 1 1 1 5 5 5 9 10 10
Output: 1 5 9 10
我给出的解决方案时间复杂度为O(n)。分而治之:
data[0]..data[data.length-1]
)。平均情况下的解决方案为 O(log(n)),仅在最坏的情况下(每个元素都不同)为 O(n)。
Java 代码:
public static List<Integer> findUniqueNumbers(int[] data) {
List<Integer> result = new LinkedList<Integer>();
findUniqueNumbers(data, 0, data.length - 1, result, false);
return result;
}
private static void findUniqueNumbers(int[] data, int i1, int i2, List<Integer> result, boolean skipFirst) {
int a = data[i1];
int b = data[i2];
// homogenous sequence a...a
if (a == b) {
if (!skipFirst) {
result.add(a);
}
}
else {
//divide & conquer
int i3 = (i1 + i2) / 2;
findUniqueNumbers(data, i1, i3, result, skipFirst);
findUniqueNumbers(data, i3 + 1, i2, result, data[i3] == data[i3 + 1]);
}
}
我认为不可能在O(n)的时间内完成。以数组包含1 2 3 4 5
为例:为了获得正确的输出,必须查看数组的每个元素,因此时间复杂度是O(n)。
n
的排序数组具有m
个不同元素,则可以完成O(mlogn)
操作。m << n (例如m=2且n=100)
时,这将非常高效。y = 第一个元素x[0]
步骤1:在x
中执行最后一次出现y
的二进制搜索(可以在O(log(n))
时间内完成)。将其索引命名为i
步骤2:y = x[i+1]
并转到步骤1m = O(n)
的情况下,该算法将表现糟糕。为了缓解这种情况,您可以与常规的O(n)
算法并行运行。 元算法由我的算法和O(n)
算法并行运行组成。 当这两个算法中的任何一个完成时,元算法停止。import java.util.*;
/**
* remove duplicate in a sorted array in average O(log(n)), worst O(n)
* @author XXX
*/
public class UniqueValue {
public static void main(String[] args) {
int[] test = {-1, -1, -1, -1, 0, 0, 0, 0,2,3,4,5,5,6,7,8};
UniqueValue u = new UniqueValue();
System.out.println(u.getUniqueValues(test, 0, test.length - 1));
}
// i must be start index, j must be end index
public List<Integer> getUniqueValues(int[] array, int i, int j) {
if (array == null || array.length == 0) {
return new ArrayList<Integer>();
}
List<Integer> result = new ArrayList<>();
if (array[i] == array[j]) {
result.add(array[i]);
} else {
int mid = (i + j) / 2;
result.addAll(getUniqueValues(array, i, mid));
// avoid duplicate divide
while (mid < j && array[mid] == array[++mid]);
if (array[(i + j) / 2] != array[mid]) {
result.addAll(getUniqueValues(array, mid, j));
}
}
return result;
}
}
a[length-1] - a[0] < length - 1
,则会出现一些重复的值。将a[0]
和a[length-1]
放入一个常数访问时间的容器(如散列表)。如果这两个值相等,那么你知道数组中只有一个唯一值,任务完成。你知道数组是已排序的。所以,如果这两个值不同,现在可以查看中间元素。如果中间元素已经在值集合中,那么你知道可以跳过整个左边的部分,并且只需递归地分析右边的部分。否则,同时递归地分析左右两部分。
根据数组中的数据,您将能够在不同数量的操作中获取所有唯一值的集合。如果所有值都相同,您可以在常数时间O(1)
内获得它们,因为您只需检查第一个和最后一个元素即可知道。如果存在"相对较少"的唯一值,则您的复杂度将接近O(log N)
,因为在每次分割后,您通常可以丢弃至少一半的分析子数组。如果所有值都是唯一的且a[length-1] - a[0] = length - 1
,您还可以在常数时间内"定义"该集合,因为它们必须是从a[0]
到a[length-1]
的连续数字。然而,为了实际列出它们,您将需要输出每个数字,而这些数字共有N个。