小明找位置 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

小朋友出操，按学号从小到大排成一列；小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。

输入描述

第一行：输入已排成队列的小朋友的学号（正整数），以空格隔开。

第二行：小明的学号；

算法复杂度要求不高于 nlog(n)。

学号为整数类型，队列规模 ≤ 10000。

输出描述

输出一个数字，代表队列位置（从 1 开始）。

示例1

输入：
93 95 97 100 102 123 155
110

输出：
6

说明：
小明排在 102 和 123 之间位于第六位。

题解

题目类型

这个题目是一个二分查找的经典应用题。通过有序数组的二分查找，找到小明应该插入的位置。

解题思路

1. 读取已排好序的学号数组和小明的学号。
2. 使用二分查找的思想，在有序数组中找到小明学号应该插入的位置。
3. 输出位置，位置从1开始计数。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 输入学生学号
        int[] stus = Arrays.stream(in.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt).toArray();

        // 小明的学号
        int no = in.nextInt();

        int l = -1, r = stus.length;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (stus[mid] < no) {
                l = mid;
            } else {
                r = mid;
            }
        }

        // 输出小明应该排的位置
        System.out.println(r + 1);
    }
}

Python

def main():
    # 输入学生学号
    stus = list(map(int, input().split()))

    # 小明的学号
    no = int(input())

    l, r = -1,  len(stus)
    while l + 1 < r:
        mid = (l + r) >> 1
        if stus[mid] < no:
            l = mid
        else:
            r = mid

    # 输出小明应该排的位置
    print(r + 1)


# 调用主函数
if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int no;
    vector<int> stus;
    while(cin >> no) stus.push_back(no);

    // 小明的学号
    no = stus.back(); stus.pop_back();

    int n = stus.size();
    int l = -1, r = n;
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        if(stus[mid] < no){
            l = mid;
        } else{
            r = mid;
        }
    }

    cout << r + 1 << endl;
    
    return 0;
} 

相关练习题

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏