在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。
实现
void test(){
//int arr[] = {2, 5, 3, 6, 6, 9, 12, 7};
int arr[] = {2, 4, 3, 9, 6, 5, 7};
//int arr[] = { 2 3 3 5 5 5 7};
//int arr[] = {1, 2, 3, 4, 5};
// int arr[] = {4, 2};
findSpecialNumber(arr, sizeof(arr)/sizeof(int));
for (int i = 0; i < sizeof(arr)/sizeof(int); i++) {
printf("arr is %d\n", arr[i]);
}
}
void findSpecialNumber(int arr[], int length){
int candidate[length];
//创建个参考数组将备份数组的内容倒序按照最大到小全部填充
//将参考数组按倒序写为右边最小值 如 2336777
//然后从左开始遍历 左侧最小值与参考数组 两者相遇既满足条件。
candidate[length - 1] = arr[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (arr[i] < candidate[i + 1]) {
candidate[i] = arr[i];
}else{
candidate[i] = candidate[i + 1];
}
}
#if 0 - 也能实现但是不太优秀
int rightMin;
rightMin = arr[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (rightMin < arr[i]) {
candidate[i] = 0;
}else if (rightMin > arr[i]){
rightMin = arr[i];
candidate[i] = arr[i];
}else{
candidate[i] = 0;
}
}
#endif
int leftMax = arr[0];
for (int i = 0; i < length; i++) {
if (leftMax < arr[i]) {
leftMax = arr[i];
}
if (leftMax == candidate[i]) {
printf("此值可以的 %d\n", leftMax);
}
}
for (int i = 0; i < length; i++) {
printf("%d", candidate[i]);
}
}