Tag Archives: 数组

hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, ... AN],已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak

输入

第一行包含一个整数N
第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)
对于30%的数据,1 ≤ N ≤ 100
对于80%的数据,1 ≤ N ≤ 1000
对于100%的数据,1 ≤ N ≤ 100000

输出

一个整数表示答案

样例输入
6
1 3 2 1 2 3
样例输出
3

给定一个数组,只包含1,2,3这三个数,问数组中有多少个三元组下标(i,j,k),满足a[i]<a[j]<a[k]。
我一开始的想法是,找出所有1,2,3出现的下标,对于每一个1的下标i,去2的下标数组中找一个lowerbound j,然后用j在3的下标数组中找一个lowerbound k,则3的下标数组中k往后的下标都是符合条件的。这需要两层循环,过了90%的数据,然后TLE了。
后来经过大神点拨,要想得到符合条件的三元组,则2一定要在中间,所以我们可以遍历原数组,对于每一个出现的2,用其左边的1的频数乘以其右边3的频数,就是这个2可以构成的合法三元组的个数。
为了不重复计算,我们可以提前算好每个位置左边和右边1和3的频数,到时候直接用left[1]*right[3]就好了。完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main() {
	//freopen("input.txt", "r", stdin);
	int n = 0;
	scanf("%d", &n);
	vector<int> nums(n, 0);
	map<int, int> left, right;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &nums[i]);
		++right[nums[i]];
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		--right[nums[i]];
		if (nums[i] == 2) {
			ans += left[1] * right[3];
		}
		++left[nums[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时18MS。

LeetCode Wiggle Sort II

LeetCode Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?


给定一个数组,对其进行wiggle排序,如果下标从0开始,则奇数下标的数都要大于其相邻两个数,即nums[0] < nums[1] > nums[2] < nums[3]....
普通解法是这样的,先给数组排序,然后设置首尾指针,分别取较小的数放到偶数位,较大的数放到奇数位。比如第一个样例排序之后是[1,1,1,4,5,6],i指向1,j指向6,开辟一个新数组,依次把nums[i++]和nums[j--]放到新数组中,形成[1,6,1,5,1,4],满足要求。
但是有一种情况会出问题,比如[4,5,5,6],按上面的方法,得到的数组是[4,6,5,5],最后的5,5不满足要求,究其原因,是因为随着i和j的推进,他们指向的数的差值越来越小,导致最后可能出现相等的情况。遇到这种情况,我们可以设置i从mid开始取,j从n-1开始取,这样i和j指向的数的差值始终是很大的,这样得到的结果就是[5,6,4,5]
因为题目说每个样例都有解,而wiggle sort的结果是先小后大,所以小数的个数总是大于等于大数的个数,比如1,2,1小数的个数大于大数的个数,1,2,1,2小数的个数等于大数的个数。所以我们i从mid开始时,如果数组有偶数个数,则中位数有两个,我们的mid应该是前一个中位数,这样能保证小数个数等于大数个数;如果数组有奇数个数,则中位数只有一个,我们的mid就从这个中位数开始,这样小数个数比大数个数多1。
所以第一个版本我们可以

class Solution {
private:
	//自己实现的快排程序
	void my_quick_sort(vector<int>& nums, int s, int t) {
		int i = s, j = t, pivot = s;
		if (i >= j)return;
		while (i <= j) {
			while (i <= j&&nums[i] <= nums[pivot])++i;
			if (i > j)break;
			while (i <= j&&nums[j] >= nums[pivot])--j;
			if (i > j)break;
			swap(nums[i++], nums[j--]);
		}
		swap(nums[pivot], nums[j]);
		my_quick_sort(nums, s, j - 1);
		my_quick_sort(nums, j + 1, t);
	}
public:
	void wiggleSort(vector<int>& nums) {
		int n = nums.size();
		my_quick_sort(nums, 0, n - 1);
		int i = (n & 1) == 0 ? n / 2 - 1 : n / 2, j = n - 1;
		vector<int> ans(n, 0);
		for (int k = 0; k < n; ++k) {
			ans[k] = (k & 1) == 0 ? nums[i--] : nums[j--];
		}
		nums = ans;
	}
};

手工写了快排程序,并手工根据n的奇偶性对i赋不同的值。本代码提交AC,用时569MS。自己写的快排是有多慢呀。
我们也可以这样

class Solution {
public:
	void wiggleSort(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int n = nums.size(), i = (n + 1) / 2, j = n;
		vector<int> ans(n, 0);
		for (int k = 0; k < n; ++k) {
			ans[k] = (k & 1) == 0 ? nums[--i] : nums[--j];
		}
		nums = ans;
	}
};

使用库中的sort,并且(n+1)/2相当于得到了偶数长的较大的中位数,或者奇数长中位数的下一个数,为了校准,进行了--i处理。本代码提交AC,用时86MS。
讨论区还有O(n)时间O(1)空间的解法,下回再战。

LeetCode K-diff Pairs in an Array

LeetCode K-diff Pairs in an Array
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won't exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

给定一个数组,问数组中绝对差值为k的unique数对有多少个。
注意数对不能有重复,比如第一个样例,虽然有两个1,但是2-diff的数对(1,3)只能算一个。
我使用的方法非常简单直白。首先因为绝对误差肯定是非负数,所以如果k<0,则直接返回0对。
然后如果k==0,则说明数对中的两个数必须相等,所以对于k==0的情况,只需要统计一下数组中有多少个重复的数。
如果k>0,则对于每一个数num,如果num+k也在数组中,则找到一个k-diff的数对。
所以为了方便查找和统计,我们首先把数和频率统计到一个map中,边map,可以边统计重复数字个数repeated。
如果k==0,直接返回repeated。
否则把map的key放到一个新的vector中,根据map的性质,这个新的vector是sorted的。则遍历sorted数组,判断每个num+k是否在map中,在则++ans。最后返回ans。
完整代码如下:

class Solution {
public:
	int findPairs(vector<int>& nums, int k) {
		if (k < 0)return 0;
		int repeated = 0;
		map<int, int> count;
		for (const auto& num : nums) {
			++count[num];
			if (count[num] == 2)++repeated;
		}
		if (k == 0)return repeated;
		vector<int> sorted;
		for (const auto& it : count) {
			sorted.push_back(it.first);
		}
		int ans = 0;
		for (const auto& num : sorted) {
			if (count.find(num + k) != count.end())++ans;
		}
		return ans;
	}
};

本代码提交AC,用时48MS。

LeetCode Maximum Product of Three Numbers

LeetCode Maximum Product of Three Numbers
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

给定一个整数数组,选出三个数,使得乘积最大。
整数数组中可能有负数,所以我们先对数组从小到大排序。如果最小值都大于0,说明没有负数,则三数乘积最大就是最大的前3个数的乘积。
如果有负数,且至少有两个负数,则还需要判断一下最小的两个负数乘以最大的正数的乘积,这个数和前一种情况的大小关系。
代码如下:

class Solution {
public:
	int maximumProduct(vector<int>& nums) {
		int n = nums.size();
		sort(nums.begin(), nums.end());
		int ans1 = nums[n - 1] * nums[n - 2] * nums[n - 3], ans2 = 0;
		if (nums[0] > 0)return ans1;
		if (nums[0] < 0 && nums[1] < 0)ans2 = nums[0] * nums[1] * nums[n - 1];
		return max(ans1, ans2);
	}
};

本代码提交AC,用时73MS。

LeetCode Maximum Distance in Arrays

LeetCode Maximum Distance in Arrays
Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
Example 1:

Input:
[[1,2,3],
 [4,5],
 [1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

  1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
  2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
  3. The integers in the m arrays will be in the range of [-10000, 10000].

给定m个已从小到大排序的数组,要求从两个不同的数组中取出两个数,使得这两个数的差的绝对值最大,问最大的差的绝对值是多少。
因为数组已排序,所以最大的差值肯定等于某个数组的最大值和另一个数组的最小值的差。这里唯一需要注意的是两个数必须选自两个不同的数组。
我开始的做法是这样的,把所有数组的最大值和最小值都拿出来,然后重新排个序。在新数组中,如果最大值和最小值来自不同的数组,则他们的差就是最终结果。加入最大值和最小值是来自同一个数组的,则求最大值和次小值的差以及次大值和最小值的差中的最大值。因为最大值和最小值来自同一个数组,所以最大值和次小值以及次大值和最小值肯定不是来自同一个数组的。
代码如下:

class Solution {
	struct P {
		int idx;
		int value;
		P(int i, int v) :idx(i), value(v) {};
		bool operator<(const P& p) {
			return this->value < p.value;
		}
	};
public:
	int maxDistance(vector<vector<int>>& arrays) {
		vector<P> vp;
		for (int i = 0; i < arrays.size(); ++i) {
			vp.push_back({ i,arrays[i][0] });
			vp.push_back({ i,arrays[i][arrays[i].size() - 1] });
		}
		sort(vp.begin(), vp.end());
		int ans = 0, n = vp.size();
		if (vp[0].idx != vp[n - 1].idx)return abs(vp[n - 1].value - vp[0].value);
		return max(abs(vp[n - 1].value - vp[1].value), abs(vp[n - 2].value - vp[0].value));
	}
};

本代码提交AC,用时26MS。因为要对m个数组的最大值和最小值排序,所以时间复杂度为O((2m)lg(2m))。
讨论区还有一种解法,只需要O(m)的复杂度。我们遍历每个数组,记录之前所有数组的最小值的最小值以及最大值的最大值,然后用当前数组的最大值和最小值减去之前所有数组中的最小值的最小值以及最大值的最大值,求绝对值,更新结果。这样就作差的两个数肯定来自不同的数组,避免了之前的问题。
代码如下:

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int ans = INT_MIN;
        int curMin = arrays[0][0], curMax = arrays[0][arrays[0].size() - 1];
        for(int i = 1; i < arrays.size(); ++i) {
            ans = max(ans, abs(arrays[i][0] - curMax));
            ans = max(ans, abs(arrays[i][arrays[i].size() - 1] - curMin));
            curMin = min(curMin, arrays[i][0]);
            curMax = max(curMax, arrays[i][arrays[i].size() - 1]);
        }
        return ans;
    }
};

本代码提交AC,用时22MS。

LeetCode Shortest Unsorted Continuous Subarray

LeetCode Shortest Unsorted Continuous Subarray
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

给定一个数组,问最短对多长的子数组排序之后,整个数组都会是升序的。比如样例对中间的[6,4,8,10,9]这个子数组排序之后,放回到原数组,原数组也是升序排列的。
第一种解法是,直接对数组排序,然后把已排序数组和未排序数组分别从首位对比,遇到第一个不相等的位置就跳出,然后需要排序的子数组长度就是j-i+1了。
代码如下:

class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		vector<int> nums_copy = nums;
		sort(nums_copy.begin(), nums_copy.end());
		int i = 0, j = nums.size() - 1;
		while (i <= j&&nums[i] == nums_copy[i])++i;
		while (j >= i&&nums[j] == nums_copy[j])--j;
		return j - i + 1;
	}
};

本代码提交AC,用时52MS,时间复杂度是O(nlgn)。
还有一种O(n)的方法,参考这个题解
基本思想是这样:

  1. 从左往右,如果该数已经在最终排序的位置了,那么该数必须小于等于该数右边的最小值
  2. 从右往左,如果该数已经在最终排序的位置了,那么该数必须大于等于该数左边的最大值

如果违反1,那么该数右边还有比该数小的数,所以需要把这个更小的数放到该数前面,也就是说该数不在其最终的位置;违反2也是类似的。
所以我们维护两个数组,分别存储从左往右的最大值和从右往左的最小值,然后和原数组比较即可。
代码如下:

/**
 *            /------------\
 * nums:  [2, 6, 4, 8, 10, 9, 15]
 * minsf:  2  4  4  8   9  9  15
 *         <--------------------
 * maxsf:  2  6  6  8  10 10  15
 *         -------------------->
 */
class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		int n = nums.size();
		vector<int> min_so_far(n, 0), max_so_far(n, 0);
		for (int i = 0, maxsf = INT_MIN; i < n; ++i)max_so_far[i] = maxsf = max(maxsf, nums[i]);
		for (int i = n - 1, minsf = INT_MAX; i >= 0; --i)min_so_far[i] = minsf = min(minsf, nums[i]);
		int i = 0, j = n - 1;
		while (i <= j&&nums[i] <= min_so_far[i])++i;
		while (j >= i&&nums[j] >= max_so_far[j])--j;
		return j - i + 1;
	}
};

本代码提交AC,用时72MS,时间复杂度是O(n),但是为啥比第一种方法还慢呀。

LeetCode Range Addition II

LeetCode Range Addition II
Given an m * n matrix M initialized with all 0's and several update operations.
Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.
You need to count and return the number of maximum integers in the matrix after performing all the operations.
Example 1:

Input:
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation:
Initially, M =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
After performing [2,2], M =
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]
After performing [3,3], M =
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]
So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won't exceed 10,000.

给定一个全为0的矩阵M,和一系列的操作,每个操作都是一对(a,b),表示要对所有i在[0,a)和j在[0,b)的元素M[i][j],问最终矩阵M中最大元素的个数。
这个题稍微想一下就会发现非常简单。
假设矩阵的左下角坐标为(0,0),对于某一个操作(a,b),表示把以(0,0)和(a,b)为对角顶点的子矩阵元素加1。那么(a1,b1)和(a2,b2)两个操作的重叠区域(0,0)-(a2,b1)所在子矩阵的元素就被加了两次,他们的值最大且相同。

所以我们只需要遍历所有操作,分别找到行和列的最小值,则他们和原点围成的子矩阵的元素值最大,且相等。
代码非常简单,如下:

class Solution {
public:
	int maxCount(int m, int n, vector<vector<int>>& ops) {
		int minRow = m, minCol = n;
		for (const auto &op : ops) {
			minRow = min(minRow, op[0]);
			minCol = min(minCol, op[1]);
		}
		return minRow*minCol;
	}
};

本代码提交AC,用时6MS。

LeetCode Subarray Sum Equals K

LeetCode Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

给定一个数组,问有多少个子数组的和等于k。
暴力方法O(n^3)肯定不行,这种连续子数组的问题,肯定会用到数组的前缀和,所以先把前缀和求出来sum[i],这样任意区间[i,j]之间的和都可以用sum[i]-sum[i-1]求到。不过还是需要O(n^2)的时间,代码如下:

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		int n = nums.size();
		if (n == 0)return 0;
		vector<int> sum(n + 1, 0);
		for (int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + nums[i - 1];
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				if (sum[j] - sum[i] == k)++ans;
			}
		}
		return ans;
	}
};

本代码提交AC,用时533MS。
看了下tag要用map来做。我们把所有前缀和及其频率存到一个map中,假设当前前缀和为sum,则如果sum-k也在map中,说明由产生sum-k前缀和的位置到当前位置的和是k。
比如样例[1,1,1],遇到第一个1时,前缀和为1,之前没有前缀和为1的情况,所以map[1]=1。当加到最后一个数时,前缀和sum=3,sum-k=1也在map中,正好说明从1开始到结束的位置的和为2,如果map[1]=2,说明有两个前缀和等于1的位置,也就有两个连续和为2的子数组。
代码如下,注意只能在遍历的同时求ans,不能等map都构建好了再求ans,这样保证前缀和为sum-k的位置肯定在i前面,也就是我们统一前缀和为k的结束位置为i,做到不重不漏。

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		int n = nums.size();
		if (n == 0)return 0;
		int ans = 0, sum = 0;
		unordered_map<int, int> cnt;
		for (int i = 0; i < n; ++i) {
			++cnt[sum];
			sum += nums[i];
			ans += cnt[sum - k];
		}
		return ans;
	}
};

本代码提交AC,用时36MS。

LeetCode Reshape the Matrix

LeetCode Reshape the Matrix
In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.
You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:

Input:
nums =
[[1,2],
 [3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

Input:
nums =
[[1,2],
 [3,4]]
r = 2, c = 4
Output:
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

  1. The height and width of the given matrix is in range [1, 100].
  2. The given r and c are all positive.

把一个n*m的矩阵按行重新组织为r*c的矩阵,相当于MATLAB的reshape函数。
简单题,新矩阵中第cnt个数,在原矩阵中的位置是(cnt/m,cnt%m)。
代码如下:

class Solution {
public:
	vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
		int n = nums.size(), m = nums[0].size();
		if (n*m != r*c)return nums;
		vector<vector<int>> ans(r, vector<int>(c, 0));
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				int cnt = i*c + j;
				ans[i][j] = nums[cnt / m][cnt % m];
			}
		}
		return ans;
	}
};

本代码提交AC,用时62MS。

LeetCode Array Partition I

LeetCode Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

给定一个长度为2n的数组,要求把数组分成n组,即(a1, b1), (a2, b2), ..., (an, bn) ,使得每组的最小值之和最大。
使用贪心策略,比如样例中,4和3肯定不能和1配对,因为1肯定是最小的,不能拿很大的数和1陪葬,所以只拿2和1配对;然后3、4配对。所以规律就是对数组排序,从小到大每两个配对。那么每组最小值之和就是第0、2、4...个数之和。
代码如下:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
    	sort(nums.begin(), nums.end());
    	int ans = 0;
    	for(int i = 0; i < nums.size(); i += 2) ans += nums[i];
    	return ans;
    }
};

本代码提交AC,用时92MS。