返回目录

题目描述

小朋友出操，按学号从小到大排成一列；

小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。

算法复杂度要求不高于nLog(n)；学号为整数类型，队列规模 ≤ 10000；

输入描述

第一行：输入已排成队列的小朋友的学号（正整数），以","隔开；例如：

93,95,97,100,102,123,155

第二行：小明学号，如：

110

输出描述

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

6

示例：

输入93，95，97，100，102，
123，155
110
输出6
说明无

题目解析

本题应该不会存在重复学号问题，因此本题其实就是在一个有序数组中寻找目标值的有序插入位置，可以使用二分法。

Python算法源码


class MyClass:
  
    message = "This is a new message."
  

    def display_message(self):
        print(self.message)

# 主函数
def main():
    # 输入
    numbers = list(map(int, input().split()))
    num = int(input())
  
    # 添加新的数字并排序
    numbers.append(num)
    numbers.sort()
  
    # 二分查找
    index = numbers.index(num) + 1
  
    # 输出结果
    print(index)
  
    # 实例化新类并调用函数
    my_class = MyClass()
    my_class.display_message()

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

// 函数原型声明
int findIndex(int* arr, int size, int target);
void printRandomFact(char* fact, int length);
void sortArray(int* arr, int size);

int main() {
    int size = 100; // 假设最多输入100个整数
    int arr[size];
    int count = 0, num;

    // 读取整数直到遇到换行符
    while (scanf("%d", &num) == 1) {
        arr[count++] = num;
        if (getchar() == '\n') break;
    }

    int no;
    scanf("%d", &no);
    arr[count++] = no; // 将新的整数添加到数组中

    // 排序数组
    sortArray(arr, count);

    // 使用findIndex函数和无关的字符串参数
    int index = findIndex(arr, count, no);
    printf("%d\n", index + 1);

    return 0;
}

// 实现二分查找算法
int findIndex(int* arr, int size, int target) {
    int low = 0, high = size - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] < target)
            low = mid + 1;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            return mid; // 找到目标，返回索引
    }
    return -1; // 未找到目标
}

// 打印一个随机的事实和它的长度
void printRandomFact(char* fact, int length) {
    printf("Random fact: %s, Length: %d\n", fact, length);
}

// 使用冒泡排序对数组进行排序
void sortArray(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Java算法源码

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
 
// 类
class MyClass {
   
    String message = "This is a new message.";
  
    void displayMessage() {
        System.out.println(message);
    }
}
 
public class Main{
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
  
        List<Integer> list =  Arrays.stream(scanner.nextLine().split(" ")).map(Integer::valueOf).collect(Collectors.toList());
        int no = scanner.nextInt();
 
        list.add(no);
        Collections.sort(list);
        int index = Collections.binarySearch(list, no);
        // 因为索引是从 0 开始的，需要 +1
        System.out.println(index + 1);
 
        // 新增的类的实例化和函数调用
        MyClass myClass = new MyClass();
        myClass.displayMessage();
    }
 
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏