【算法】Split Array With Same Averag

作者: 无良剑染 | 来源:发表于2020-02-15 17:33 被阅读0次

    题目

    In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

    Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

    Example :
    Input:
    [1,2,3,4,5,6,7,8]
    Output: true
    Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
    Note:

    The length of A will be in the range [1, 30].
    A[i] will be in the range of [0, 10000].

    数组 A 的长度为 1 ~ 30, A 中元素为大小为 0 ~ 10000 的整数,求 A 是否可以拆分为两个子数组 B 和 C,且 B 和 C 中元素加和的平均值相等。

    解题思路

    假设 A 可以拆分成符合条件的 B、C,A、B、C 的长度分别为 n、i、n-i ,则sumA/n == sumB/i == sumC/(n-i)。
    由于所有元素均为整数,所以 sumA、sumB、sumC 均为整数,则 sumB == sumAi/n 为整数,则 sumAi%n == 0。
    由于 1<=n<=30,1<=i<=n/2<=15,所以可以通过 sumA*i%n == 0 先寻找可能符合条件的 i 。
    在找到 i 后,可以求出 sumB ,用 isExist 方法来判断 A 中是否存在 i 个元素加和为 sumB 的子数组。
    isExist 方法中,通过 sumB 逐一减去元素,i-1,并进行递归,若最后 sumB 和 i 同时减为 0 ,说明有 i 个元素加和为 sumB,否则说明 i 不符合条件。

    代码实现

    Runtime: 16 ms
    Memory: 20.8 MB

    func splitArraySameAverage(_ nums: [Int]) -> Bool {
            // n 为 nums 的长度
            let n = nums.count
            // 长度为 0 或者 1 时,说明长度无法形成符合的分拆,返回 false
            if n < 2 { return false }
            // sum 为 nums 加和
            let sum = nums.reduce(0, +)
            // 循环 1 到 n/2
            for i in 1 ... n/2 {
                // 若存在 i 符合 (sum * i) % n == 0 则可能成功拆分成 i 和 n-i 个元素的符合的子数组
                if ((sum * i) % n == 0) {
                    // 判断 nums 中从 nums[0] 开始,是否存在 i 个元素取得加和为 sum * i / n
                    if isExist(nums, i, 0, sum * i / n) {
                        // 若可以 ,则符合条件,返回 true
                        return true
                    }
                }
            }
            // 走到这里说明没有符合条件的 i ,返回 false
            return false
        }
        
        // 判断 nums 中从 nums[len] 开始,是否存在 idx 个元素取得加和为 sum
        func isExist(_ nums: [Int], _ len: Int, _ idx: Int, _ sum: Int) -> Bool {
            // 由于用的是加和值递减元素值得方法,所以当 sum 和 len 均为 0 时,说明是符合条件的,返回 true
            if sum == 0, len == 0 { return true }
            // idx len sum 非法时,返回 false
            if idx >= nums.count || len < 0 || sum < 0 { return false }
            // 从 idx 遍历到 end ,进行递归,用 sum-nums[i],同事 len 长度 -1 ,i 起始索引 +1
            for i in idx..<nums.count {
                // 若 nums[i] == nums[i - 1] ,因为重复操作,可以跳过本次循环
                if i > idx && nums[i] == nums[i - 1] { continue }
                if isExist(nums, len - 1, i + 1, sum - nums[i]) { return true }
            }
            // 走到这里,没有遇到符合条件的 sum len,则返回 false
            return false
        }
    

    代码地址:https://github.com/sinianshou/EGSwiftLearning

    相关文章

      网友评论

        本文标题:【算法】Split Array With Same Averag

        本文链接:https://www.haomeiwen.com/subject/vpjyfhtx.html