Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
What is wrong with my code ??
map<int,int> m;
for(int i = 0 ; i < nums.size() ; i ){
m[nums[i]] ;
if(m[nums[i]] > 2)nums.erase(nums.begin() i);
}
return nums.size();
CodePudding user response：
From the given text, we can derive the following requirements
- Given an integer array nums
- sorted in non-decreasing order,
- remove some duplicates in-place such that each unique element appears at most twice.
- The relative order of the elements should be kept the same.
- Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums.
- More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result.
- It does not matter what you leave beyond the first k elements
- Return k after placing the final result in the first k slots of nums.
So, after elicitating the requirements, we know that we have a fixed size array, presumably (because of the simplicity of the task) a C-Style array or a C std::array. Because of the shown source code, we assume a std::array.
It will be sorted in increasing order. Their shall be an in-place removal of elements. So, no additional variables. The rest of the requirements already shows the solution.
--> If we find duplicates (more than 2) we will shift the rest of the values one to the left and overwrite one of the duplicates. Then the logical number of elements in the array will be one less. So, the loop must run one step less.
This ends up in a rather simple program:
#include <iostream>
#include <array>
// Array with some test values
constexpr int ArraySize = 25;
std::array<int, ArraySize> nums{ 1,2,2,2,3,3,3,4,4,4,4,4,6,5,5,5,5,5,6,6,6,6,6,6,9,9 };
int main() {
// Currentlogical end of the data in the array. In the beginning, last value in the array
size_t endIndex = nums.size();
// Check allelments from left to tright
for (size_t index = 0; index < endIndex;) {
// Check, if 3 elements are same
if ((index < (endIndex -2)) and nums[index] == nums[index 1] and nums[index 1] == nums[index 2]) {
// Yes, found 3 same elements. We willdelete one, so the endIndex needs to be decremented
--endIndex;
// Now hsift all array elements one to the left
for (size_t shiftIndex = index 2; shiftIndex < endIndex; shiftIndex)
nums[shiftIndex] = nums[shiftIndex 1];
}
else index;
}
// SHow result
std::cout << endIndex << '\n';
}
CodePudding user response：
I can offer the solution of your problem.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void showContentSet(set<int>& input)
{
for(auto iterator=input.begin(); iterator!=input.end(); iterator)
{
cout<<*iterator<<", ";
}
return;
}
void showContentVector(vector<int>& input)
{
for(int i=0; i<input.size(); i)
{
cout<<input[i]<<", ";
}
return;
}
void solve()
{
vector<int> numbers={1, 2, 1, 3, 4, 5, 7, 5, 8, 5, 9, 5};
set<int> indicesToDelete;
for(int i=0; i<numbers.size(); i)
{
int count=0;
for(int j=0; j<numbers.size(); j)
{
if(numbers[i]==numbers[j])
{
count;
if(count>2)
{
indicesToDelete.insert(j);
}
}
}
}
cout<<"indicesToDelete <- ";
showContentSet(indicesToDelete);
int newOrder=0;
cout<<endl<<"Before, numbers <- ";
showContentVector(numbers);
for(auto iterator=indicesToDelete.begin(); iterator!=indicesToDelete.end(); iterator)
{
numbers.erase(numbers.begin() (*iterator-newOrder));
newOrder;
}
cout<<endl<<"After, numbers <- ";
showContentVector(numbers);
cout<<endl;
return;
}
int main()
{
solve();
return 0;
}
Here is the result:
indicesToDelete <- 9, 11,
Before, numbers <- 1, 2, 1, 3, 4, 5, 7, 5, 8, 5, 9, 5,
After, numbers <- 1, 2, 1, 3, 4, 5, 7, 5, 8, 9,
CodePudding user response：
I suggest using a frequency array.
frequency array works, That you count how many duplicates of each number while inputting, It's stored usually in an array called freq, Also can be stored in a map<int, int> or unordered_map<int, int>.
And because of input is in non-decreasing order, outputting this solution will be easy.
Note: this solution won't work if input numbers is bigger than 10^5
Solution:
#include <iostream>
const int N = 1e5 1; // Maximum size of input array
int n;
int nums[N], freq[N];
int main()
{
// Input
std::cin >> n;
for (int i = 0; i < n; i )
{
std::cin >> nums[i];
freq[nums[i]] ;
}
// Outputting numbers, Using frequency array of it
for (int i = 0; i < N; i )
{
if (freq[i] >= 1)
std::cout << i << ' ';
if (freq[i] >= 2)
std::cout << i << ' ';
}
return 0;
}
CodePudding user response：
This is basically a conditional copy operation. Copy the entire range, but skip elements that have been copied twice already.
The following code makes exactly one pass over the entire range. More importantly it avoids erase operations, which will repeatedly shift all elements to the left.
vector<int> nums; // must be sorted already
if (nums.size()<=1)
return; // already done
// basically you copy all elements inside the vector
// but copy them only if the requirement has been met.
// `in` is the source iterator. It increments every time.
// `out` is the destination iterator. It increments only
// after a copy.
auto in=nums.begin();
auto out=nums.begin();
// current is the current 'int' value
int current=*in;
// `count` counts the repeat count of the current value
int count=0;
while (in!=nums.end()) {
if (*in==current) {
// The current value repeats itself, so increment
// the count value
count;
} else {
// No, this is a new value.
// initialise current and count
current=*in;
count=1;
}
if (count<=2) {
// only if at most two elements of the same value
// copy the current value to `out`
*out=current;
out;
}
// try next element
in;
}
// out points to the last valid element 1