题目
数组A中任意两个相邻元素大小相差1,现给定这样的数组A和目标整数t,找出t在数组A中的位置。如数组:[1,2,3,4,3,4,5,6,5],找到4在数组中的位置。
思路
这道题目最差时间复杂度也是O(N),所以重点在于能不能找到一种尽可能减少比较次数的方法。
如数组:[1,2,3,4,3,4,5,6,5],找到4在数组中的位置。4和1比较,差为3,那么即使最好情况(递增或者递减),4也就是在a[3]的位置,可以跳过a[1]a[2]。这样在特定数组(目标值和a[1]相差很大)的情况下或许可以节省时间。
所以得出规律:对于目标t,由当前位置a[i]比较开始,下一个可能位置为i = abs(a[i]-t)
代码
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
int Find(int num[],int n,int target){
if(n <= 0){
return -1;
}
for(int i = 0;i < n;){
if(num[i] == target){
return i;
}
i += abs(num[i] - target);
}
return -1;
}
};
int main() {
Solution solution;
int num[] = {1,2,3,2,3,4,3,2,3};
int target = 4;
cout<<solution.Find(num,9,target)<<endl;
}
上面只是返回第一个目标位置,如果题目要求返回所有的目标位置代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> Find(int num[],int n,int target){
vector<int> result;
if(n <= 0){
return result;
}
for(int i = 0;i < n;){
if(num[i] == target){
result.push_back(i);
i += 2;
}
else{
i += abs(num[i] - target);
}
}
return result;
}
};
int main() {
Solution solution;
int num[] = {1,2,3,4,3,4,3,2,3,2,3,4};
int target = 4;
vector<int> result = solution.Find(num,12,target);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<endl;
}
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
1.数组求和?(用递归,只用一行代码) 2.求数组的最大值和最小值(用递归的方法,将数组分为左右两个子数组,返回条件是左右数组只剩一个或两个元素)
java基础面试题旋转数组的最小数字本资源系百度网盘分享地址
java基础面试题二维数组中查找本资源系百度网盘分享地址
给定一个整数数组 nums 和一个整数目标值 target,请您在该数组中找出两个元素的和等于目标值,并返回这两个元素的索引。
java基础面试题把数组排成最小的数
嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题
java基础面试题数组中重复的数字本资源系百度网盘分享地址
简介:在这个Java编程示例中,我们展示了如何有效地查找整数数组中的最大值。通过一个名为 `findMax` 的自定义方法,我们演示了如何遍历数组并找到其中的最大元素。无论您是初学者还是有经验的Java开发者,本示例都...
面试题53 - I. 在排序数组中查找数字 I题目链接面试题53 - I. 在排序数组中查找数字 I题目描述统计一个数字在排序数组中出现的次数。题解public
请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104025402
数组 - 需要参加面试的人
java面试 java面试_leetcode面试题解之第34题在排序数组中查找元素的第一个和最后一个位置_java题解
java基础面试题数组中只出现一次的数字本资源系百度网盘分享地址
java基础面试题数组中出现次数超过一半的数字本资源系百度网盘分享地址
java基础面试题调整数组顺序使奇数位于偶数前面本资源系百度网盘分享地址
java基础面试题数组中逆序对本资源系百度网盘分享地址
面试题总结:数组和链表的区别 数组和链表.pdf
文章目录1:题目2:python实现2.1:思路12.1.1:代码...请找出数组中任意一个重复的数字。 示例 1: 输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 限制: 2 <= n <= 100000 来源:力扣(LeetCode) 链接:http
java基础面试题数字在排序数组中出现的次数本资源系百度网盘分享地址