在数组a中查找最大值x，以便-x也能在使用C代码时使用(面试问题)
在数组a中查找最大值x，以便-x也能在使用C代码时使用(面试问题)
提问于 2020-02-11 23:22:09
得到整数的数组a。需要返回a中的最大值a，以便-x也在a中。如果没有这样的值-返回0。
示例：
对于[6,5,2,-1,-2,-5]，返回值是5，因为-5在数组中(答案不是6，因为-6不在数组中)。
编辑：输入数组不一定排序。
现在，如果我可以使用HashSet来解决这个问题，我将使用HashSet来解决这个问题，我将将所有数组元素的绝对值添加到其中，遍历数组并更新最大值，如果它是我迄今为止看到的最大值，如果我在Hash中找到了它的绝对值。这将导致O(n)平均时间。
但在采访中，我需要使用C代码来解决这个问题，而不需要创建任何像HashSet这样的特殊数据结构。
我唯一的想法是对数组进行排序，使用两个指针(一个用于开始，一个用于结束)，并将指针移动到彼此之间，直到找到答案。这还不够好，因为它是O(nlogn)。
您知道如何在O(n)中使用C代码来解决这个问题，只使用内置库吗？
回答 1
Stack Overflow用户
发布于 2020-02-12 09:32:29
#include <stdio.h>
#include <stdlib.h>
int found = 0;
int n = 0;
int len = 6; // your array has 6 elements
for(int i = 0; i < len -1; i++) {
for(int j = i+1; j < len; j++) {
if(a[i] == -a[j] && (found = 0 || abs(a[i] > n)) n = abs(a[i]);
}
}
if(found) printf("Number is : %d\n", n);
else printf("Not found");好，这是真正的没有库的O(n)解决方案，但是需要一个有序的数组。只需一个循环，并移动指针的初始和最终。
#include <stdio.h>
int a[] = {6,5,2,-1,-2,-5};
int main(int argc, char** argv) {
int* left = a; // point to first
int* right = a + 5; // point to last
while(right > left) {
int result = *left + *right;
if(!result) {
printf("Number is %d\n", *left);
return 0;
}
if(result > 0) left++;
else right--;
}
printf("No result");
return 1;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60178824
复制相关文章
相似问题
腾讯云开发者
