题目链接

左侧严格小于计数

题目描述

给定一个长度为 n 的整数序列 a，你需要计算并生成一个新的结果序列 b。对于 b 中的每一个元素 b[i]，它的值是原始序列 a 中，所有在 a[i] 左边（即索引 j < i）且数值上严格小于 a[i] 的元素个数。

输入描述: 第一行输入一个整数 n (1 ≤ n ≤ 1000)。 第二行输入 n 个整数 a[1], a[2], ..., a[n]，用空格分隔。

输出描述: 在一行内输出 n 个整数，表示结果序列 b，用空格分隔。

解题思路

本题要求我们对序列中的每一个元素，都执行一次计数操作。这个计数操作的对象是该元素左侧的所有元素。这是一个非常适合使用嵌套循环解决的问题。

算法步骤 (暴力解法):

  1. 读取输入: 首先，读取整数 n，然后将 n 个整数读入一个数组或列表 a 中。同时，可以创建一个同样大小的数组 b 来存放结果。

  2. 外层循环: 使用一个 for 循环遍历数组 a 中的每一个元素，从索引 i = 0 到 n-1。这个循环负责为 b[i] 计算相应的值。

  3. 内层循环: 在外层循环的每一次迭代中（即对于每一个 a[i]），我们需要再启动一个内层循环。这个内层循环的作用是遍历 a[i] 左侧的所有元素。因此，它的索引 j 应该从 0 遍历到 i-1。

  4. 比较和计数: 在内层循环中，我们进行比较。如果 a[j] < a[i]，说明找到了一个满足条件的元素，我们就让一个计数器 count 加一。

  5. 存储结果: 当内层循环结束后，count 的值就是 a[i] 左侧所有比它小的元素的总数。我们将这个 count 值存入 b[i]。

  6. 输出: 当外层循环完全结束后，数组 b 就被完全填充了。最后，按格式要求将数组 b 的所有元素输出。

举例说明: 假设输入序列 a 为 [4, 4, 2, 1, 3, 5]，我们来计算 b[4] (对应 a[4]=3) 的值：

  • 外层循环到 i=4，a[4]=3。初始化 count = 0。
  • 内层循环 j 从 0 到 3：
    • j=0, a[0]=4. 4 < 3 不成立。
    • j=1, a[1]=4. 4 < 3 不成立。
    • j=2, a[2]=2. 2 < 3 成立，count 变为 1。
    • j=3, a[3]=1. 1 < 3 成立，count 变为 2。
  • 内层循环结束，b[4] 被赋值为 2。

这种 O(n^2) 的解法对于本题的数据范围来说效率是足够的。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    vector<int> b(n);
    
    // 外层循环遍历每个元素 a[i]
    for (int i = 0; i < n; ++i) {
        int count = 0;
        // 内层循环遍历 a[i] 左侧的所有元素 a[j]
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                count++;
            }
        }
        b[i] = count;
    }
    
    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << b[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int[] b = new int[n];
        
        // 外层循环
        for (int i = 0; i < n; i++) {
            int count = 0;
            // 内层循环
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {
                    count++;
                }
            }
            b[i] = count;
        }
        
        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.print(b[i] + (i == n - 1 ? "" : " "));
        }
        System.out.println();
    }
}

n = int(input())
a = list(map(int, input().split()))

b = []
# 外层循环遍历a的每个元素和其索引
for i, current_val in enumerate(a):
    count = 0
    # 内层循环只遍历当前元素左侧的部分
    # a[:i] 是 a 从开头到索引i-1的切片
    for left_val in a[:i]:
        if left_val < current_val:
            count += 1
    b.append(count)

# 使用*解包和sep参数来格式化输出
print(*b)

算法及复杂度

  • 算法：暴力枚举 / 嵌套循环。
  • 时间复杂度：。我们使用了两层嵌套循环，外层循环运行 N 次，内层循环平均运行约 N/2 次，总计算量级为 N*N。
  • 空间复杂度：。我们使用了两个大小为 N 的数组来分别存储输入序列和结果序列。