首页 > 试题广场 >

计算数组的小和

[编程题]计算数组的小和
  • 热度指数：10045 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
数组小和的定义如下：
(其中 的定义是第 i 个数的左侧小于等于 的个数)

例如，数组 s = [1, 3, 5, 2, 4, 6] ，在 s[0] 的左边小于或等于 s[0] 的数的和为 0 ； 在 s[1] 的左边小于或等于 s[1] 的数的和为 1 ；在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3=4 ；在 s[3] 的左边小于或等于 s[3] 的数的和为 1 ；
在 s[4] 的左边小于或等于 s[4] 的数的和为 1+3+2=6 ；在 s[5] 的左边小于或等于 s[5] 的数的和为 1+3+5+2+4=15 。所以 s 的小和为 0+1+4+1+6+15=27
给定一个数组 s ，实现函数返回 s 的小和

数据范围： ，

输入描述:
第一行有一个整数N。表示数组长度
接下来一行N个整数表示数组内的数


输出描述:
一个整数表示答案
示例1

输入

6
1 3 5 2 4 6

输出

27
示例2

输入

1
1

输出

0

备注:

算法知识视频讲解
添加回答
Java
我去你家头像 我去你家
我用的是树状数组，这个和逆序对一样的，先离散化后直接查询就行，我觉得这个比分治简单多了，我是看了左神的那个视频来的
import 题目.抢红包;

import javax.management.Query;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
import java.util.concurrent.ConcurrentLinkedDeque;

public class Main{
static class Input{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
 StreamTokenizer in =new StreamTokenizer(br);
 public int nextInt() throws IOException{
in.nextToken();
 return (int) in.nval;
 }
}
public static int getBit(int x){
return x&(-x);
 }
public static int getSum(int x){  //看看那个这个数之前的前缀和，也就是小和
int ans=0;
 while (x>0){
ans+=bit[x];
 x-=getBit(x);
 }
return ans;
 }
public static void setBit(int x,int sum){ //x是下标，sum是要改变的数
while (x<bit.length){
bit[x]+=sum;
 x+=getBit(x);
 }
}
static int[] bit = new int[100005];
 public static void main(String[] args)throws IOException {
Input sc = new Input();
 int n =sc.nextInt();
 int[] nums = new int[n];
 Set<Integer> set = new TreeSet<>();
 Map<Integer,Integer> map = new HashMap<>();
 for (int i = 0; i < n; i++) {
nums[i]=sc.nextInt();
 set.add(nums[i]);
 }
int t=1;
 for (Integer a:set
) {
map.put(a,t++);  //离散化
 }
int ans=0;
 for (int i = 0; i < n; i++) {
ans+=getSum(map.get(nums[i])); //这个数前面比他小的和，我没有直接插入全部
 setBit(map.get(nums[i]),nums[i]);  //一个一个插入
 }
System.out.println(ans);
 }
}
发表于 2023-12-27 11:52:24 回复(0)
Java
pein531头像 pein531
左老师课堂上的经典例题，在归并排序时计算小和，时间复杂度为O(n*logn) 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static long smallSum = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strNums = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = Integer.parseInt(strNums[i]);
        mergeSort(nums, 0, nums.length - 1);
        System.out.println(smallSum);
    }
    
    private static void mergeSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        mergeCount(nums, left, mid, right);
    }
    
    private static void mergeCount(int[] nums, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, p = 0;
        while(p1 <= mid && p2 <= right){
            smallSum += nums[p1] <= nums[p2] ? (right - p2 + 1) * nums[p1]: 0;
            help[p ++] = nums[p1] <= nums[p2]? nums[p1 ++]: nums[p2 ++];
        }
        while(p1 <= mid)
            help[p ++] = nums[p1 ++];
        while(p2 <= right)
            help[p ++] = nums[p2 ++];
        for(int i = 0; i < help.length; i++)
            nums[left + i] = help[i];
    }
}

发表于 2021-11-13 12:37:45 回复(2)
Java
myorange头像 myorange

这一题很合适用树状数组去解，在往树状数组中插入值时，pos为arr[i] + 100, 值为arr[i]

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        System.out.println(getMinSum(arr));
    }
    private static final int OFFSET = 100;
    private static long getMinSum(int[] arr) {
        int maxV = arr[0];
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] > maxV) {
                maxV = arr[i];
            }
        }
        BIT bit = new BIT(maxV + OFFSET);
        long sum = 0;
        for (int i = 0; i < arr.length; ++i) {
            sum += bit.sum(arr[i] + OFFSET);
            bit.add(arr[i] + OFFSET, arr[i]);
        }
        return sum;
    }
}
class BIT {
    int n;
    long[] bit;
    public BIT(int n) {
        this.n = n;
        bit = new long[n + 1];
    }
    void add(int pos, int val) {
        while(pos <= n) {
            bit[pos] += val;
            pos += lowbit(pos);
        }
    }
    long sum(int pos) {
        long res = 0;
        while(pos > 0) {
            res += bit[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
    private int lowbit(int x) {
        return x & (-x);
    }
}
发表于 2021-09-23 14:33:10 回复(0)
Java
牛客112642938号头像 牛客112642938号 
import java.util.*;
public class Main{
    public static int[] tmp=new int[100000];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[] arr=new int[N];
        for(int i=0;i<N;i++){
            arr[i]=sc.nextInt();
        }
        
        long count=getMinSum(arr,0,N-1);
        System.out.println(count);
    }
    
    public static long merge(int[] arr,int left,int mid,int right){
        int len=arr.length;
        
        int i=left,j=mid+1;
        int k=0;
        long res=0;
        
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                res += (right-j+1)*arr[i];
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=right) tmp[k++]=arr[j++];
        
        for(i=left,k=0;i<=right;i++){
            arr[i]=tmp[k++];
        }
        return res;
    }
    
    public static long getMinSum(int[] arr,int left,int right){
        if(left==right) return 0;
        int mid=(left+right)/2;
        long lSum=getMinSum(arr,left,mid);
        long rSum=getMinSum(arr,mid+1,right);
        if(arr[mid]<=arr[mid+1]){
            long tmpSum=0;
            for(int i=left;i<=mid;i++){
                tmpSum += arr[i];
            }
            return lSum+rSum+tmpSum*(right-mid);
        }
        long crossSum=merge(arr,left,mid,right);
        
        return lSum+rSum+crossSum;
    }
}
主要思想是利用归并排序，将数组划分为两部分  [left,mid]和[mid+1,right]，归并排序的过程是先拆分，直到不可拆分，即，左右两部分都只有一个数，只有一个数，这两部分肯定是有序的，再根据大小合并回去。
所以，在这里，可以默认[left,mid]和[mid+1,right]这两部分都是有序的，
     整个数组的小和=数组左半部分贡献的小和+数组右半部分贡献的小和+左右两部分之间贡献的小和
整个思路大概是这样，然后具体看左右两部分之间贡献的小和，这里有两个可以优化的地方：
1. 左半部分最大值<=右半部分最小值时   ，即  arr[mid]<=arr[mid+1] 时，左半部分的值都比右半部分的小，所以 左右两部分之间贡献的小和=sum(left,mid)*(右半部分元素的个数)，然后直接返回对应结果
2. 拷贝数组要使用一个全局变量，尽量不要定义在merge函数中，递归的过程中可能存在很多次调用，定义在merge函数中，每次都要经历一次 重新分配一次内存，调用完后释放内存的过程，在递归深度很深时，这个是非常耗时的，所以拷贝数组要尽量使用一个全局变量。
发表于 2021-06-09 10:26:21 回复(0)
Java
Castile头像 Castile
看了一下没有java版本的，注意两个细节， 这个题目的小和，当左边的数字和当前的数相等时，也算一个小和。所有循环里面的判断if 应该是 <= 。然后就是help数组，的大小应为high-low+1， 注意拷贝回原数组的细节： 

import java.util.Scanner;

/**
 *
 * @author Hongliang Zhu
 * @create 2020-02-29 22:53
 */
public class Main {
    // 暴力方法 O(N^2)
    public static long  smallSum(int[] arr){
        long sum = 0;
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]){
                    sum+=arr[j];
                }
            }
        }
        return sum;
    }

    public static long samllSum_merge(int[] arr, int low, int high){
        if(low == high) return 0;
        // 计算mid的位置
        int mid = low + (( high - low ) >> 1); // 这样可以避免溢出，而且使用了位运算，效率更高
        return samllSum_merge(arr, low, mid) + samllSum_merge(arr, mid+1, high) + merge(arr, low, mid, high);
    }
    // 归并两个有序的数组
    public static long merge(int[]arr, int low, int mid, int high){
        int[] help = new int[high - low + 1];
        long result = 0;
        int p = low;
        int q = mid + 1;
        int k = 0;
        while (p <= mid && q <= high){
            if(arr[p] <= arr[q]){ //  左边比又变小，产生小和
                result += arr[p] * ( high - q + 1);
                help[k++] = arr[p++];
            }else if(arr[p] > arr[q]){
                help[k++] = arr[q++];
            }
        }
        while(p <= mid){
            help[k] = arr[p++];
            k++;
        }
        while(q <= high){
            help[k] = arr[q++];
            k++;
        }
        // copy
        for(int i = 0; i < high - low + 1; i++){
            arr[low + i] = help[i];
        }
        return result;
    }


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i <n; i++){
            arr[i] = scanner.nextInt();
        }
        long sum =  samllSum_merge(arr,0, arr.length -1);

        System.out.println(sum);

    }

}


发表于 2020-03-01 12:27:02 回复(3)
提交观点

问题信息

二分 排序
上传者：小小
难度：
5条回答 8441浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号