数组按升序排列,需要找出重复的数字 需要一个时间复杂度为logn的程序
int n[] = {1, 2, 3, 4, 5, 5, 6};
int size = sizeof[n];
int mid;
mid = size/ 2 ;
if (a[mid] == a[mid + 1])
printf("%d",a[mid]);
return a[mid];
else if (a[mid] != a[mid + 1])
for(int i=0;i<mid;i++){
if(a[i]==a[mid+1])
return a[i];
}
else
for(int i=mid ;mid<size;i++){
if(a[mid]==a[mid+1])
return a[mid];
}
最佳答案
如果您假设数字必须从 0 开始并以 1 递增,您可以将中间值与索引进行比较。如果中间相同,则较高,如果中间不同,则较低。
这将为您提供二分搜索时间 O(log2 N)。唯一的区别是您正在与索引进行比较,而不是与固定值进行比较。 示例:int n[] = {0,1, 2, 3, 4, 5, 5, 6}; 注:数字以0开头 如果数字以 1 开头,则相应地更改索引
int findDuplicate(int array[],int n) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high)/2;
int midVal = array[mid];
if (midVal == mid)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
关于c 程序使用 logn 时间复杂度查找升序数组中的重复元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41488134/