给定一个从小到大排列的有序整数数组a[n](n≤10
6
)和一个整数k，输出k在数组中的最大下标（从0开始），如果数组中不存在该数，则输出-1。
从数组中a[n-1]开始，直到a[0]倒序找k，找到返回对应下标，找不到返回-1
不知道你这个问题是否已经解决, 如果还没有解决的话:这就好办了，我们很好得出
我们只需要一个对N(<10)的循环, 代入题目的公式，然后计算出验证的结果再和 你输入的数进行比较 这样就满足了条件。
#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstdio>
using namespace std;
string inttostring(int in) { // 标准的数字转字符串
stringstream os;
os << in;
string od;
os >> od;
return od;
}
bool check(int sum, int c) { // 检查末尾的函数 方法是倒着检查
string ssum = inttostring(sum);
string cc = inttostring(c);
for (int i = cc.size() - 1, j = ssum.size() - 1;i >= 0;i--, j--) {
if (cc[i] != ssum[j]) {
return false;
}
}
return true;
}
bool find_NK(int& n, int& k, int inp) { // 寻找N,K的函数 使用了题目的要求
k = n = -0x3f3f3f3f;
for (n = 1;n <= 10;n++) {
k = inp * inp * n;
if (check(k, inp)) {
k = (int)sqrt(k * 1.0 / n);
return true;
}
}
return false;
}
#include <vector>
int main(int argc, char** argv) { // 主函数 调用各个模块
int N, K;
int t, inp;
scanf("%d", &t);
for (int tv = t;tv--;) {
scanf("%d", &inp);
bool pl = find_NK(N, K, inp);
if (pl) {
printf("%d %d\n", N, N * K * K);
}
else {
cout << "No" << endl;
}
}
system("pause");
return 0;
}
我可以解决该问题。
解决方案如下:
遍历整个有序整数数组，逐一比较每个元素与所要查找的整数，直到找到相等的元素或者比所要查找的整数大的元素，此时结束遍历，输出找到的元素下标。
如果遍历整个数组之后仍然没有找到相等的元素，则输出-1。
代码如下:
def find_max_index(arr, target):
"""
在有序整数数组arr中查找元素target的最大下标
"""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2 # 用二分法查找元素target在arr中的位置
if arr[mid] == target:
# 找到了相等的元素，继续往右查找，直到找到最后一个相等的元素
while mid < len(arr) - 1 and arr[mid+1] == target:
mid += 1
return mid
elif arr[mid] < target:
# 如果中间元素比目标元素小，则在右半部分查找
low = mid + 1
else:
# 如果中间元素比目标元素大，则在左半部分查找
high = mid - 1
# 没有找到相等的元素
return -1
数组长度最大为可以达到Python列表的最大长度，大概是10^7左右。当然，具体取决于系统内存的大小。