LeetCode解题报告（265）-- 1649. Create Sorted Array through Instructions
Posted onEdited onViews: Valine:
Problem
Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:
The number of elements currently in nums that are strictly less thaninstructions[i].
The number of elements currently in nums that are strictly greater thaninstructions[i].
For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].
Return the total cost to insert all elements frominstructionsintonums. Since the answer may be large, return it modulo109 + 7
Example 1:
1 2 3 4 5 6 7 8
Input: instructions = [1,5,6,2] Output: 1 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 5 with cost min(1, 0) = 0, now nums = [1,5]. Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6]. Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6]. The total cost is 0 + 0 + 0 + 1 = 1.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: instructions = [1,2,3,6,5,4] Output: 3 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 2 with cost min(1, 0) = 0, now nums = [1,2]. Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3]. Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6]. Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6]. Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6]. The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.
Example 3:
1 2 3 4 5 6 7 8 9 10 11 12 13
Input: instructions = [1,3,3,3,2,4,2,1,2] Output: 4 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3]. Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3]. Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4]. Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4]. Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4]. Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4]. The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.
classSolution { int smaller[100001]; int sorted[100001]; int count[100001]; int temp[100001]; int M = 1e9 + 7; public: intcreateSortedArray(vector<int>& instructions){ int size = instructions.size(); for (int i = 0; i < size; i++) { sorted[i] = instructions[i]; } helper(instructions, 0, size - 1); longlong result = 0; for (int i = 0; i < size; i++) { result += min(smaller[i], i - smaller[i] - count[instructions[i]]); result %= M; count[instructions[i]]++; } return result; } private: voidhelper(vector<int>& nums, int a, int b){ if (a >= b) { return; } int mid = (a + b) / 2; helper(nums, a, mid); helper(nums, mid + 1, b); for (int i = mid + 1; i <= b; i++) { auto iter = lower_bound(sorted + a, sorted + mid + 1, nums[i]); smaller[i] += iter - (sorted + a); } // merge int i = a, j = mid + 1, p = 0; while (i <= mid && j <= b) { if (sorted[i] <= sorted[j]) { temp[p] = sorted[i]; i++; } else { temp[p] = sorted[j]; j++; } p++; } while (i <= mid) { temp[p] = sorted[i]; i++; p++; } while (j <= b) { temp[p] = sorted[j]; j++; p++; } for (int i = 0; i < b - a + 1; i++) { sorted[a + i] = temp[i]; } } };
classSolution { public: intcreateSortedArray(vector<int>& instructions){ longlong result = 0; int size = instructions.size(); for (int i = 0; i < size; i++) { update(instructions[i], 1); longlong a = sumRange(1, instructions[i] - 1); longlong b = sumRange(instructions[i] + 1, MAX_N); result += min(a, b); result %= M; } return result; } private: int bitArr[MAX_N + 1]; // 1-index intlowbit(int x){ return x & (-x); } int M = 1e9 + 7; voidupdate(int i, longlong d){ while (i <= MAX_N) { bitArr[i] += d; bitArr[i] %= M; i += lowbit(i); } } longlongqueryPreSum(int i){ longlong ans = 0; while (i) { ans += bitArr[i]; ans %= M; i -= lowbit(i); } return ans; } longlongsumRange(int i, int j){ return queryPreSum(j) - queryPreSum(i - 1); } };
