JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-10-19
目录

数组的均值分割Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中,使得 A 数组和 B 数组不为空,并且 average(A) == average(B) 。

如果可以完成则返回true , 否则返回 false  。

注意:对于数组 arr ,  average(arr) 是 arr 的所有元素除以 arr 长度的和。

示例 1:

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

示例 2:

输入: nums = [3,1]
输出: false

提示:

  • 1 <= nums.length <= 30
  • 0 <= nums[i] <= 104

# 思路

//np问题,不能暴搜,需要加去重和提前退出的判断来缩短时间

# 解法


class Solution {

    //np问题,不能暴搜,需要加去重和提前退出的判断来缩短时间

    public boolean splitArraySameAverage(int[] A) {
        int len = A.length;
        int sum = 0;//sum为总和
        for(int i = 0; i < len; i++){
            sum += A[i];
        }
        Arrays.sort(A);        
        //从小到大排序,从0开始处理较少数据
        for(int i = 1; i <= len/2; i++){
            int remainder = sum * i % len;
            //首先确认能否整除
            int target = sum * i / len;
            //这是目标和
            if(remainder == 0 && helper(A,0,i,target))
                return true;
        }
        return false;
    }
    
    public boolean helper(int[] A, int begin, int len, int target){
        if(len == 0) 
            return target == 0;
        if(target < len * A[begin])
            return false;
        for(int i = begin; i <= A.length - len; i++){
            //略去重复的情况,缩短运行时间
            if(i > begin && A[i] == A[i-1]) continue;
            if(helper(A, i+1, len-1, target- A[i]))
                return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式