查询插入位置

查询插入位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 1process.stdin.resume();
 2process.stdin.setEncoding('utf-8');
 3let input = '';
 4
 5process.stdin.on('data', (data) => {
 6    input += data;
 7});
 8
 9process.stdin.on('end', () => {
10    // 去除输入字符串两端的空白字符
11    const trimmedInput = input.trim();
12    // 将输入字符串按空格分割成数组，并转换为数字
13    const inputParts = trimmedInput.split(' ').map(Number);
14
15    // 假设数组部分和目标值部分是通过空格分隔的，且数组部分在目标值部分之前
16    // 我们取输入数组的前 n-1 个元素作为升序数组 nums，最后一个元素作为目标值 target
17    const n = inputParts.length;
18    const nums = inputParts.slice(0, n - 1);
19    const target = inputParts[n - 1];
20
21    // 实现查找或确定插入位置的函数
22    function findInsertPosition(nums, target) {
23        let left = 0;
24        let right = nums.length - 1;
25        let index = -1;
26
27        while (left <= right) {
28            const mid = Math.floor((left + right) / 2);
29            if (nums[mid] === target) {
30                index = mid;
31                break;
32            } else if (nums[mid] < target) {
33                left = mid + 1;
34            } else {
35                right = mid - 1;
36            }
37        }
38
39        // 如果没有找到目标值，则返回应该插入的位置
40        return index !== -1 ? index : left;
41    }
42
43    // 调用函数并输出结果
44    const result = findInsertPosition(nums, target);
45    console.log(result);
46
47    process.exit();
48});

Copyright ©2010-2022 比特日记 All Rights Reserved.

Powered By 可尔物语

浙ICP备11005866号-12