龙空技术网

2022-01-18:将数组分成两个数组并最小化数组和的差。 给你一个长

福大大架构师每日一题 416

前言:

目前同学们对“java数组拆分两个数组”大体比较看重,同学们都需要知道一些“java数组拆分两个数组”的相关资讯。那么小编同时在网络上搜集了一些有关“java数组拆分两个数组””的相关资讯,希望各位老铁们能喜欢,小伙伴们快快来学习一下吧!

2022-01-18:将数组分成两个数组并最小化数组和的差。

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组,分别求出两个数组的和,并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回 最小 的数组和之差。

输入:nums = [3,9,7,3]。

输出:2。

解释:最优分组方案是分成 [3,9] 和 [7,3] 。

数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

力扣2035。

答案2022-01-18:

分治法。

arr -> 8 0 1 2 3 4 5 6 7

process(arr, 0, 4) [0,4)

process(arr, 4, 8) [4,8)

arr -> 8 0 1 2 3 4 5 6 7

process(arr, 0, 4) [0,4)

process(arr, 4, 8) [4,8)

arr[index....end-1]这个范围上,去做选择

pick挑了几个数!

sum挑的这些数,累加和是多少!

map记录结果

HashMap<Integer, TreeSet<Integer>> map

key -> 挑了几个数,比如挑了3个数,但是形成累加和可能多个!

value -> 有序表,都记下来!

整个过程,纯暴力!2^15 -> 3万多,纯暴力跑完,依然很快!

代码用golang编写。代码如下:

package mainimport (    "fmt"    "math"    "sort")func main() {    ret := minimumDifference([]int{3, 9, 7, 3})    fmt.Println(ret)}func minimumDifference(arr []int) int {    size := len(arr)    half := size >> 1    //HashMap<Integer, TreeSet<Integer>> lmap = new HashMap<>();    lmap := make(map[int]map[int]struct{})    process(arr, 0, half, 0, 0, lmap)    //HashMap<Integer, TreeSet<Integer>> rmap = new HashMap<>();    rmap := make(map[int]map[int]struct{})    process(arr, half, size, 0, 0, rmap)    sum := 0    for _, num := range arr {        sum += num    }    ans := math.MaxInt64    for leftNum, _ := range lmap {        for leftSum, _ := range lmap[leftNum] {            rr := rmap[half-leftNum]            //模拟treeset            rarr := make([]int, 0)            for r, _ := range rr {                rarr = append(rarr, r)            }            sort.Ints(rarr)            ri := NearestIndex2(rarr, (sum>>1)-leftSum)            rightSum := 0            if ri != -1 {                rightSum = rarr[ri]                pickSum := leftSum + rightSum                restSum := sum - pickSum                //ans = Math.min(ans, restSum - pickSum);                if ans > restSum-pickSum {                    ans = restSum - pickSum                }            }        }    }    return ans}// arr -> 8   0 1 2 3      4 5 6 7// process(arr, 0, 4)  [0,4)// process(arr, 4, 8)  [4,8)// arr[index....end-1]这个范围上,去做选择// pick挑了几个数!// sum挑的这些数,累加和是多少!// map记录结果// HashMap<Integer, TreeSet<Integer>> map// key -> 挑了几个数,比如挑了3个数,但是形成累加和可能多个!// value -> 有序表,都记下来!// 整个过程,纯暴力!2^15 -> 3万多,纯暴力跑完,依然很快!func process(arr []int, index int, end int, pick int, sum int, map0 map[int]map[int]struct{}) {    if index == end {        if _, ok := map0[pick]; !ok {            map0[pick] = make(map[int]struct{})        }        map0[pick][sum] = struct{}{}    } else {        process(arr, index+1, end, pick, sum, map0)        process(arr, index+1, end, pick+1, sum+arr[index], map0)    }}// 在arr上,找满足<=value的最右位置func NearestIndex2(arr []int, v int) int {    L := 0    R := len(arr) - 1    index := -1 // 记录最右的对号    for L <= R {        mid := L + (R-L)>>1        if arr[mid] <= v {            index = mid            L = mid + 1        } else {            R = mid - 1        }    }    return index}

执行结果如下:

***

[左神java代码]()

[moonfdd]()

标签: #java数组拆分两个数组