LintCode 31. 数组划分 JavaScript算法
程序员文章站
2022-03-24 17:44:20
...
描述
给出一个整数数组 nums 和一个整数 k。划分数组(即移动数组 nums 中的元素),使得:
- 所有小于k的元素移到左边
- 所有大于等于k的元素移到右边
返回数组划分的位置,即数组中第一个位置 i,满足 nums[i] 大于等于 k。
说明
你应该真正的划分数组 nums,而不仅仅只是计算比 k 小的整数数,如果数组 nums 中的所有元素都比 k 小,则返回 nums.length。
样例
- 例1:
输入:[],9
输出:0
- 例2:
输入:[3,2,2,1],2
输出:1
解释:真实的数组为[1,2,2,3].所以返回 1
挑战
使用 O(n) 的时间复杂度在数组上进行划分。
解析
当两个数不同时,a + b = (a ^ 2 - b ^ 2)/(a - b);
当两个数相同时,a + b = 2 * a 或者 2 * b;
const aplusb = function (a, b) {
if(a === b) return 2 * a
else return (Math.pow(a,2)-Math.pow(b,2)) / (a-b)
}
运行结果
推荐阅读
-
javascript中数组的常用算法深入分析
-
重读《学习JavaScript数据结构与算法-第三版》- 第3章 数组(二)
-
LintCode 1266. 找不同 JavaScript算法
-
LintCode 41. 最大子数组 JavaScript算法
-
LintCode 767. 翻转数组 JavaScript算法
-
LintCode 1099. 不下降数组 JavaScript算法
-
LintCode 1347. 尾随零 JavaScript算法
-
LintCode 1314. 2的幂 JavaScript算法
-
LintCode 4. 丑数 II JavaScript算法
-
LintCode 34. N皇后问题 II JavaScript算法