获取单值网格的最小操作数

题目描述

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

样例

样例输入

grid = [[2,4],[6,8]], x = 2
grid = [[1,5],[2,3]], x = 1
grid = [[1,2],[3,4]], x = 2

样例输出

4
解释：可以执行下述操作使所有元素都等于 4 ：
2 加 x 一次。
6 减 x 一次。
8 减 x 两次。
共计 4 次操作。

5
解释：可以使所有元素都等于 3 。

-1
解释：无法使所有元素相等。

提示

• $m==grid.length$
• $n==grid[i].length$
• $1<=m,n<=10^5$
• $1<=m\ast n<=10^5$
• $1<=x,grid[i][j]<=10^4$

思路

第一个测试用例具误导性，因为第一个测试用例中，所有数字变为4所需的操作次数与变为6的所需操作次数一样。
最初思路就是通过一定的操作数使所有数都变为中位数。因为中位数的性质，所有数变为中位数的所需操作数肯定是最小的。

代码实现

class Solution {public int minOperations(int[][] grid, int x) {List<Integer> list = new ArrayList<>();int m = grid.length, n = grid[0].length;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){// 所有数组的差值都必须是x的倍数，不然无法通过+-x改变成为指定值。if(Math.abs(grid[0][0] - grid[i][j]) % x != 0) return -1;list.add(grid[i][j]);}}int ans = 0;Collections.sort(list);int k = list.get(n * m / 2);for(int i = 0; i < list.size(); i++){ans += Math.abs(list.get(i) - k) / x;}return ans;}
}

下一个排列

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
  整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。

• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
  给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

样例

样例输入

nums = [1,2,3]
nums = [3,2,1]
nums = [1,1,5]

样例输出

[1,3,2]
[1,2,3]
[1,5,1]

提示

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

思路

最初思路，从后枚举nums[i]，并且维护已经所有已枚举过的最小值，如果当前nums[i] < 维护的最小值，那么交换两个值。并且记录当前交换的下标i,之后在对i+1 ~ n-1区间内进行排序即可。主要实现难点就是局部排序，可以说很麻烦。

之后看的题解理解咯另外一种思路，从后枚举一定是有单调性的，在单调的基础上直接反转这个局部区间即可。（反转局部区间使用双指针很方便）

代码实现

class Solution {public void nextPermutation(int[] nums) {int i = nums.length - 2;while(i >= 0 && nums[i] >= nums[i+1]) i--;if(i >= 0){int j = nums.length - 1;while(j >= 0 && nums[i] >= nums[j]) --j;swap(nums, i, j);}int l = i + 1, r = nums.length - 1;while(l < r){swap(nums, l, r);r--;l++;}}private void swap(int[] nums, int a, int b){int tmp = nums[a];nums[a] = nums[b];nums[b] = tmp;}private void reverse(int[] nums, int l, int r){while(l < r){swap(nums, l, r);r--;l++;}}
}