欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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)
}

运行结果

LintCode 31. 数组划分 JavaScript算法

LintCode 31. 数组划分 JavaScript算法