#Coding-Data View

数组-划分

难点：

需要对每个划分点遍历所有位置
划分点之间相互关联，动了一个另一个可能就不满足

常见划分依据:

大小关系(有序)
部分和

题目

1013. Partition Array Into Three Parts With Equal Sum

找两个下标i,j(inclusive) 使得:

1	subarray_sum[0, i] = subarray_sum[i+1, j] = subarray_sum[j+1, n-1]

为了避免下标移动后重新计算子数组和，我想到了滑动窗口

因为题目要求每个划分部分非空，所以i最小从1开始，最大到n-3。j最大从n-2开始，最小到2。

1 2	i: 1 -> n-3 j: n-2 -> 2

这样就是O( n^2 )的时间复杂度

想复杂了！

548. Split Array with Equal Sum

找三个下标i,j,k(exclusive)使得：

1	subarray_sum[0, i-1] = subarray_sum[i+1, j-1] = subarray_sum[j+1, k-1] = subarray_sum[k-1, n-1]

蛮力办法:

对每个可能i,j,k遍历。固定一个，再移动另一个。时间会到 O( n^3 )

O( n^2 )的办法：

固定j,两边分别确定i,k

def splitArray(self, nums):
       n = len(nums)
       s = [0] * (n + 1)
       for i in range(n): s[i + 1] = s[i] + nums[i]
       def check(l, r):
           return set(s[m] - s[l] for m in range(l + 1, r + 1) if s[m] - s[l] == s[r + 1] - s[m + 1])
       return any(check(0, j - 1) & check(j + 1, n - 1) for j in range(n))

769. Max Chunks To Make Sorted

无序数组是[0, 1, ..., arr.length - 1]的一个排列，该怎么利用这个条件？

也就是说每个数字都有固定的位置，如果不在那个位置上就说明至少有两个元素的位置是错乱的。

转载: C++ 复杂度O(n)方法详解双100%-100)

思路

由于题目规定了数组是数[0, N - 1]的排列，所以最终排好序后，数组下标为i的数一定是i，即arr[i] == i。那么在初始数组中，如果arr[i] != i，为了让arr[i]回到对应的下标上，我们必须将下标i和下标arr[i]放到同一个分组中。

具体地，例如[1, 2, 0, 3, 4]，从左往右遍历数组，分组数初始化res = 0：

Step 1. 下标0上的数是1，1要位于下标1的位置上，所以当前分组包含的下标最大值应为1，而当前下标为0，所以当前无法分组，res = 0；

Step 2. 下标1上的数是2，2要位于下标2的位置上，所以当前分组包含的下标最大值应为2，而当前下标为1，所以当前无法分组，res = 0；

Step 3. 下标2上的数是0，0要位于下标0的位置上，所以当前分组包含的下标最大值仍应为2，当前下标也为2，说明此位置之前的数中不包含比2大的数，可以在当前位置分组，res = 1；

Step 4. 下标3上的数是3，3已经位于下标3的位置上，所以当前分组包含的下标最大值应为3，当前下标也为3，说明此位置之前的数中不包含比3大的数，可以在当前位置分组，res = 2；

Step 5. 下标4上的数是4，4已经位于下标4的位置上，所以当前分组包含的下标最大值应为4，当前下标也为4，说明此位置之前的数中不包含比4大的数，可以在当前位置分组，res = 3；

768. Max Chunks To Make Sorted II

这里数组不再是[0, 1, ..., arr.length - 1]的一个排列，而且包含重复元素。

按照769. Max Chunks To Make Sorted的思路，应该是找到当前分组的一个最大值，769中的最大值确定的方式是通过下标index和当前的最大值curMax相等来确定的(i == curMax)

这里改如何界定分组呢？

可以确定的是下标应该不能再作为一个参照

转载: Java Solution beats 99.9% with detailed example and explanation

Problem Invariant: For an element, if all the numbers to its left are smaller or equal to all the numbers to its right, we can always insert a split point between the element and its next element which separate the array into two parts and after we sort the two parts individually, the concatenation of them will be a sorted array.

i:       0  1   2   3  4
arr[i]   2  1 | 3   4  4
maxLeft  2 '2'  3   4  4
minRight 1  1  '3'  4  4

when i = 1, maxLeft[i] <= minRight[i + 1] (maxLeft[i] includes the i-th number itself but minRight[i +1] only counts the numbers to its right), then we can insert a split point between index 1 and 2.

数组-划分

题目

Comments: