一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
这是一个 交互式问题 )
给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index,就请返回 -1。
何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:
首先,A.length >= 3
其次,在 0 < i < A.length - 1 条件下,存在 i 使得:
A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1]
你将 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:
MountainArray.get(k) - 会返回数组中索引为k 的元素(下标从 0 开始) MountainArray.length() - 会返回该数组的长度
注意:
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外,任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
分作两步就清晰好多了:
1.把峰值找出來2.按峰值把其分为左右两部分,先二分查找左边,左边没有再看右边
/**
* @param {number} target
* @param {MountainArray} mountainArr
* @return {number}
*/
var findInMountainArray = function (target, mountainArr) {
// 一 查找峰值
let left = 0
let right = mountainArr.length() - 1
let mid = left + ((right - left) >> 1)
while (left <= right) {
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) { // 当mid小于右边的时,说明峰值在右边, 继续在右边查找
left = mid + 1
} else { // 否则在左边, 继续在左边查找
right = mid - 1
}
mid = left + ((right - left) >> 1)
}
// 执行完上边的二分查找 left 就是峰值的下标了
// 二 根据峰值分两段 二分查找
let res = -1
res = binarySearch(mountainArr, 0, left, target, true)
res === -1 && (res = binarySearch(mountainArr, left, mountainArr.length() - 1, target, false))
return res
};
/**
* @param {MountainArray} mountainArr
* @param {number} left
* @param {number} right
* @param {number} target
* @param {Boolean} isUp
* @return {number}
*/
function binarySearch(mountainArr, left, right, target, isUp) {
let mid = left + ((right - left) >> 1) // 获取中间索引
while (left <= right) {
let midValue = mountainArr.get(mid)
if (midValue === target) return mid // 找到直接返回
if (midValue < target) {
isUp ? left = mid + 1 : right = mid - 1 //用 isUp 区分正序还是降序
} else {
isUp ? right = mid - 1 : left = mid + 1
}
mid = left + ((right - left) >> 1)
}
return -1
}
1.Object.defineProperty无法监控到数组下标的变化,导致通过数组下标添加元素,不能实时响应;2.Object.defineProperty只能劫持对象的属性,从而需要对每个对象,每个属性进行遍历,如果,属性值是对象,还需要深度遍历。Proxy可以劫持整个对象,并返回一个新的对象。3.Proxy不仅可以代理对象,还可以代理数组。还可以代理动态增加的属性。
Proxy有以下两个优点;
可以劫持整个对象,并返回一个新对象 有13种劫持操作
[1]
1095. 山脉数组中查找目标值: https://leetcode-cn.com/problems/find-in-mountain-array/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!