第 k1 小和第 k2 小元素之间的所有元素之和

2025年3月17日 | 阅读 10 分钟

引言

有效计算数组中第 k1 个和第 k2 个最小元素之间项的总和

是数据分析、算法设计和统计等多个领域面临的一个关键挑战。

在本文中，我们将探讨三种不同的方法来应对这一挑战。

我们将探讨传统的排序方法、基于选择算法的方法和基于线段树的解决方案。

每种技术在时间、空间和实现复杂度方面都有不同的权衡。

复杂度。

复杂性。

例如，考虑下面的数组

arr = [7, 10, 4, 3, 20, 15]

我们想计算此数组中位于第二小和第五小元素之间的所有条目的总和。

第五小。

解决方案

1. 以非递减顺序排序数组得到

arr = [3, 4, 7, 10, 15, 20]

2. 检索第 k1 个和第 k2 个最小元素

给定 k1 = 2 和 k2 = 5，第二小元素（第 k1 个）是 4，第五小元素

最小元素（第 k2 个）是 15。

3. 计算 k1 和 k2 最小项之间组件的总和

现在，我们遍历已排序的数组，并累加所有介于 4 和 15 之间的条目。
介于 4 和 15 之间的元素是 4、7、10、15。
因此，这些组件的总和是 4 + 7 + 10 + 15 = 36。

所以，在这种情况下，数组 [7, 10, 4, 3, 20, 15] 中第二小和第五小条目之间所有项的总和

数组 [7, 10, 4, 3, 20, 15] 中所有项的总和是 36。

方法一：基于排序的方法

基于排序的方法是一种简单的方法，用于计算数组中第 k1 个和第 k2 个最小成员之间项的总和。

成员。让我们看看这个策略的每个阶段以及它的工作原理

它如何运作

1. 排序数组

第一步是以非递减顺序对数组进行排序。这可以通过

通过快速排序或归并排序等高效排序算法完成。排序数组使得

很容易识别第 k1 个和第 k2 个最小项，它们将在排序后位于

排序后位于索引 k1-1 和 k2-1 处。

2. 获取第 k1 个和第 k2 个最小元素

排序数组后，我们可以从相应位置访问第 k1 个和第 k2 个最小项。

这些项反映了我们必须计算总和的范围的下限和上限。

我们必须计算总和的范围的下限和上限。

3. 计算总和

要计算总和，请在已排序的数组中识别第 k1 个和第 k2 个最小项。

然后，累加这些限制之间（包括限制本身）的所有元素。这需要遍历

遍历已排序的数组并添加 [k1-1, k2-1] 之间的元素。

伪代码

function SumBetweenKthSmallest(arr, k1, k2):
    1. Sort the array arr in non-decreasing order.
    2. Retrieve the k1'th and k2'th smallest elements from the sorted array arr.
    3. Initialize the sum to 0.
    4. Iterate over each element elem in arr:
       - If elem is greater than or equal to the k1'th smallest element and less than or equal to the k2'th smallest element:
         - Add elem to sum.
    5. Return the sum as the result.

时间复杂度

使用高效排序方法对数组进行排序需要 O(n log n) 时间。
检索第 k1 个和第 k2 个最小项需要常量时间。
遍历数组并添加其元素需要 O(n) 时间。
这种方法的总体时间复杂度为 O(n log n)，其中排序步骤占据了大部分时间。

实施

import java.util.Arrays;
public class SumBetweenKthSmallest {
    public static int sumBetweenKthSmallest(int[] arr, int k1, int k2) {
Arrays.sort(arr);
        int k1_smallest = arr[k1 - 1];
        int k2_smallest = arr[k2 - 1];
        int sum = 0;
        for (int i = 0; i<arr.length; i++) {
            if (arr[i] >= k1_smallest &&arr[i] <= k2_smallest) {
                sum += arr[i];
            }
        }
        return sum;
    }
    public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
        int k1 = 2;
        int k2 = 5;
        int result = sumBetweenKthSmallest(arr, k1, k2);
System.out.println("Sum of elements between the " + k1 + "th and " + k2 + "th smallest elements: " + result);
    }
}

输出

The sum of all elements between k1'th and k2'th smallest elements

说明

我们首先使用 arrays.Sort(arr) 对数组进行非递减排序。它在原地对数组进行排序，并保证最小项 k1 和 k2 分别在索引 k1-1 和 k2-1 处排序。
排序后，我们从数组中提取第 k1 个和第 k2 个最小条目。
然后，我们遍历已排序的数组，通过验证每个元素是否落在 [k1-1, k2-1] 范围内来计算第 k1 个和第 k2 个最小元素之间项的总和。
最后，我们返回计算出的总和。

方法二：基于选择算法的方法

基于选择算法的技术是一种有效的方法，可以在不完全排序数组的情况下找到第 k1 个和第 k2 个最小项。

最小项。让我们分解此技术的阶段以了解其工作原理。

了解它是如何工作的。

1. 实现选择算法。

选择过程，例如 Quickselect，用于高效地发现数组的第 k1 个和第 k2 个最小项。
Quickselect 是一种随机方法，它使用快速排序的分区机制。它选择一个枢轴元素并将数组分成两个子数组，左边是小于枢轴的元素，右边是大于枢轴的元素。
通过根据第 k1 个和第 k2 个最小组件的索引递归查找合适的划分，Quickselect 有效地缩小了搜索空间，直到找到所需的元素。

2. 遍历数组以计算总和

在使用 Quickselect 确定第 k1 个和第 k2 个最小项后，我们遍历数组一次以计算它们之间的元素总和。
在遍历过程中，我们累加所有落在 k1 和 k2 处最小元素提供的范围内的组件。

3. 复杂度分析

这种方法比基于排序的策略更快，特别是对于更大的数据集，

因为 Quickselect 的预期时间复杂度为 O(n)。但是，

选择方法的递归性质需要比基于排序的技术更复杂的

实现比基于排序的技术更复杂。

伪代码

function quickselect(arr, low, high, k):
    if low == high:
        return arr[low]
pivot_index = random.randint(low, high)
pivot_index = partition(arr, low, high, pivot_index)
    if k == pivot_index:
        return arr[k]
    else if k <pivot_index:
        return quickselect(arr, low, pivot_index - 1, k)
    else:
        return quickselect(arr, pivot_index + 1, high, k)
function partition(arr, low, high, pivot_index):
pivot_value = arr[pivot_index]
swap(arr, pivot_index, high)
i = low
    for j from low to high - 1:
        if arr[j] <pivot_value:
swap(arr, i, j)
i++
swap(arr, i, high)
    return i
function sumBetweenKthSmallest(arr, k1, k2):
    n = length of arr
    k1_smallest = quickselect(arr, 0, n - 1, k1 - 1)
    k2_smallest = quickselect(arr, 0, n - 1, k2 - 1)
    sum = 0
    for i from 0 to n - 1:
        if arr[i] >= k1_smallest and arr[i] <= k2_smallest:
            sum += arr[i]
    return sum

实施

import java.util.Random;
public class SumBetweenKthSmallest {
    public static int quickSelect(int[] arr, int low, int high, int k) {
        if (low == high)
            return arr[low];
        int pivotIndex = partition(arr, low, high);
        int pivotRank = pivotIndex - low + 1;
        if (k == pivotRank)
            return arr[pivotIndex];
        else if (k <pivotRank)
            return quickSelect(arr, low, pivotIndex - 1, k);
        else
            return quickSelect(arr, pivotIndex + 1, high, k - pivotRank);
    }
    public static int partition(int[] arr, int low, int high) {
        int pivotIndex = new Random().nextInt(high - low + 1) + low;
        int pivot = arr[pivotIndex];
swap(arr, pivotIndex, high);
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
swap(arr, i, j);
i++;
            }
        }
swap(arr, i, high);
        return i;
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
    }
    public static int sumBetweenKthSmallest(int[] arr, int k1, int k2) {
        int k1_smallest = quickSelect(arr, 0, arr.length - 1, k1);
        int k2_smallest = quickSelect(arr, 0, arr.length - 1, k2);
        int sum = 0;
        for (int num : arr) {
            if (num>= k1_smallest &&num<= k2_smallest) {
                sum += num;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
        int k1 = 2;
        int k2 = 5;
        int result = sumBetweenKthSmallest(arr, k1, k2);
System.out.println("Sum of elements between the " + k1 + "th and " + k2 + "th smallest elements: " + result);
    }
}

输出

说明

quickSelect 方法是 Quickselect 算法的修改版本，它返回数组中第 k 个最小元素。
partition 方法是 Quickselect 的实用函数，它根据枢轴元素对数组进行分区。
为了找到数组中最小的项，我们在 k1 和 k2 位置使用 quickSelect。
找到最小的项后，我们遍历数组一次并计算它们之间元素的总和。
最后，我们将计算出的总和作为结果返回。

方法三：基于线段树的方法

基于线段树的方法是一种有效解决数组上范围查询的有效方法。

范围查询。在这种方法中，我们预处理数组以创建线段树，

线段树是一种二叉树，每个节点都包含有关原始数组中指定范围元素的信息。

原始数组。线段树中的每个节点表示一个索引范围，并保存

该范围内项的聚合信息，例如总和、最小值和最大值。

以下是如何使用基于线段树的技术来计算数组中第 k1 个和第 k2 个最小元素之间的项的总和。

第 k1 个和第 k2 个最小元素之间的项的总和。

1. 构建线段树

我们首先为指定的数组创建一个线段树。线段树通过将数组分成更小的段来迭代构建，直到每个段包含一个单独的条目。在线段树的每个节点，我们存储相关索引范围内项的总和。

2. 查询线段树

一旦线段树构建完成，我们就可以轻松查询它，以发现第 k1 个和第 k2 个最小元素之间项的总和。
我们从根遍历线段树到对应于包含第 k1 个和第 k2 个最小项的范围的节点。
通过聚合这些节点中包含的信息，我们可以确定落在指定索引内的组件的总和。

3. 复杂度分析

基于线段树的技术提供了高效的范围查询功能，在初始预处理后，每次查询的时间复杂度为 O(log n)。

初始预处理后，每次查询的时间复杂度为 O(log n)。尽管创建

线段树需要 O(n log n) 时间，但后续搜索可以快速执行，

这使得此方法适用于需要重复范围查询的情况。

伪代码

function buildSegmentTree(arr, tree, node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) / 2
buildSegmentTree(arr, tree, 2 * node + 1, start, mid)
buildSegmentTree(arr, tree, 2 * node + 2, mid + 1, end)
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
function querySegmentTree(tree, node, start, end, k1, k2):
    if k2 < start or k1 > end:
        return 0
    else if k1 <= start and k2 >= end:
        return tree[node]
    else:
        mid = (start + end) / 2
leftSum = querySegmentTree(tree, 2 * node + 1, start, mid, k1, k2)
rightSum = querySegmentTree(tree, 2 * node + 2, mid + 1, end, k1, k2)
        return leftSum + rightSum
function sumBetweenKthSmallest(arr, k1, k2):
    n = length of arr
    tree = new Array[4 * n]
buildSegmentTree(arr, tree, 0, 0, n - 1)
    return querySegmentTree(tree, 0, 0, n - 1, k1 - 1, k2 - 1)

实施

public class SegmentTree {
int[] segmentTree;
    public SegmentTree(int[] arr, int n) {
        int height = (int) Math.ceil(Math.log(n) / Math.log(2));
        int maxSize = 2 * (int) Math.pow(2, height) - 1;
segmentTree = new int[maxSize];
buildSegmentTree(arr, 0, 0, n - 1);
    }
    private void buildSegmentTree(int[] arr, int node, int start, int end) {
        if (start == end) {
segmentTree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
buildSegmentTree(arr, 2 * node + 1, start, mid);
buildSegmentTree(arr, 2 * node + 2, mid + 1, end);
segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2];
        }
    }
    public int query(int k1, int k2, int n) {
        return querySegmentTree(0, 0, n - 1, k1 - 1, k2 - 1);
    }
    private int querySegmentTree(int node, int start, int end, int k1, int k2) {
        if (k1 <= start && k2 >= end) {
            return segmentTree[node];
        }
        if (end < k1 || start > k2) {
            return 0;
        }
        int mid = (start + end) / 2;
        return querySegmentTree(2 * node + 1, start, mid, k1, k2) +
querySegmentTree(2 * node + 2, mid + 1, end, k1, k2);
    }
    public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
        int n = arr.length;
SegmentTreesegTree = new SegmentTree(arr, n);
        int k1 = 2;
        int k2 = 5;
        int sum = segTree.query(k1, k2, n);
System.out.println("Sum of elements between the " + k1 + "th and " + k2 + "th smallest elements: " + sum);
    }
}

输出

说明

1. 构建线段树

在启动阶段，我们从提供的数组中创建一个线段树。线段树是递归创建的。在树的每个节点，我们记录相应索引中元素的总和。

2. 查询线段树

为了获取第 k1 个和第 k2 个最小元素之间项的总和，我们在线段树上使用范围查询。
我们遍历线段树，递归查询相应的段，直到我们到达必要的索引。

3. 示例用法

在主函数中，我们使用提供的数组构建 SegmentTree 类的实例。
我们指示最小组件 k1 和 k2 的范围，我们希望计算它们的总和。
最后，我们调用查询方法来查找指定第 k1 个和第 k2 个最小元素之间的总和并打印结果。

下一个主题二叉索引树范围更新和点查询

← 上一个下一个 →

第 k1 小和第 k2 小元素之间的所有元素之和

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

第 k1 小和第 k2 小元素之间的所有元素之和

相关帖子

最小化数组中的偏差

循环列表应用

双向链表上的归并排序

后缀树导论

最大化硬币，使根到叶子路径和为正

数组的应用、优点和缺点

总行程距离

检测并移除链表中的循环

下一个回文数

融合 vs 堆叠

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器