package daily.mid

import java.util.*
import kotlin.Comparator

fun main() {
    // 870. 优势洗牌
    // https://leetcode.cn/problems/advantage-shuffle/
    println(advantageCount(intArrayOf(2,7,11,15), intArrayOf(1,10,4,11)).contentToString())
}

fun advantageCount(nums1: IntArray, nums2: IntArray): IntArray {
    // 数组长度
    val n = nums1.size
    // nums1 从小到大排序
    nums1.sort()

    val indices = Array<Int>(n) {
        it
    }
    // 排序之后，indices[0] 就是 nums2 最小值的下标，indices[n-1] 就是 nums2 最大值的下标
    Arrays.sort(indices, object : Comparator<Int> {
        override fun compare(o1: Int?, o2: Int?): Int {
            if (o1 == null || o2 == null) {
                return 0
            }
            return nums2[o1] - nums2[o2]
        }
    })
    // 排序之后，indices[left] 就是 nums2 最小值的下标，indices[right] 就是 nums2 最大值的下标
    var left = 0
    var right = n - 1
    val ans = IntArray(n)
    // nums1 已经排过序，从左到右遍历 nums1
    // 如果 nums1[i] > nums2[indices[left]]，
    // 那 nums1[i] 就是 nums1 中，比 nums[indices[left]] 大，且是大得最少的，那 nums1[i] 就可以填充到 ans[indices[left]] 中
    // 如果 nums1[i] <= nums2[indices[left]]，
    // 那  nums1[i] 就用不上了，用 nums[i] 和 nums2 的最大值，也就是 nums2[indices[right]] 碰掉（nums[i] 填充到 ans[indices[right]]）
    for (i in nums1.indices) {
        // ans 的下标和 nums2 是同步的
        if (nums1[i] > nums2[indices[left]]) {
            ans[indices[left]] = nums1[i]
            left++
        }else {
            ans[indices[right]] = nums1[i]
            right--
        }
    }
    return ans
}

fun advantageCount1(nums1: IntArray, nums2: IntArray): IntArray {
    // 用田忌赛马的思想，用 nums1 的最小值 min1，去试探 nums2 的最小值 min2，如果 min1 > min2，则优势+1
    // 如果 min1 <= min2，则用 min1 去碰掉 nums2 的最大值 max2
    // 因为要保持 nums2 的顺序，所以不能直接对 nums2 排序，可以定义一个新的数组 indices，初始化 indices[i] = i
    // 根据 nums2 对 indices 排序，这样依赖，indices[0] 就是 nums2 最小元素的下标，indices[indices.size-1] 就是 nums2 最大元素的下标

    // 先对 nums1 排序
    nums1.sort()
    // 定义 indices 数组，初始化 indices[i]=i
    val indices = Array(nums2.size) {
        it
    }
    // 根据 nums2 对 indices 排序，这样依赖，indices[0] 就是 nums2 最小元素的下标，indices[indices.size-1] 就是 nums2 最大元素的下标
    Arrays.sort(indices) {i1, i2 ->
        nums2[i1].compareTo(nums2[i2])
    }
    val result = IntArray(nums1.size)
    // 指向 indices 的左右指针
    var left = 0
    var right = indices.size - 1
    for (i in nums1.indices) {
        if (nums1[i] > nums2[indices[left]]) {
            // nums1[i] 是优势的
            result[indices[left]] = nums1[i]
            left++
        }else {
            // nums[i] 是劣势的，碰掉 nums2 的最大值
            result[indices[right]] = nums1[i]
            right--
        }
    }
    return result
}