在数组中查找重复项-语法解释

Question

我对这个语法int *count = new int[sizeof(int)* (size - 2)]一无所知

将创建什么样的数组。

我以为他们正试图创建类似地图的结构。但它是如何工作的呢？

#include <bits/stdc++.h>
using namespace std;

void printRepeating(int arr[], int size)
{
int *count = new int[sizeof(int)*(size - 2)];
int i;

cout << " Repeating elements are ";
for(i = 0; i < size; i++)
{
if(count[arr[i]] == 1)
cout << arr[i] << " ";
else
count[arr[i]]++;
}
}

// Driver code
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
return 0;
}

// This is code is contributed by rathbhupendra

Answer 1

在数组中查找重复当然是一个已解决的问题。IMHO一个非常简单的解决方案是：

1. 使用std:：sort((对数组进行排序
2. 使用循环检查元素是否等于其后续元素，即for(int i = 1; i < num_elements; i++){ if(arr[i-1]==arr[i]){...duplicate!...}}

这需要O(n(内存和O(n*log(n((时间，所以这很好。你也可以使用哈希图，但基本相同。

---

无论如何，对于您的问题：

int *count = new int[sizeof(int)* (size - 2)]; 

这是不正确的。我假设它曾经是这个C代码：

int num_elements = size-2; // we want size-2 elements (not sure why)
int total_bytes = sizeof(int) * num_elements; 
int *count = calloc(total_bytes); // reserve space, and set to 0

哪一个可以翻译成这个C++代码：

int num_elements = size-2; 
int * count = new int[num_elements]{0}; // alloc and set to zero

所以做移植的人误解了C++的基本原理。

让我们进一步挖掘。

---

因此，问题公式似乎是：

您将得到一个n+2个元素的数组。数组的所有元素在1到n的范围内。除两个元素外，所有元素都出现一次出现两次的数字。找出两个重复的数字

我做了一些微小的更改，使解决方案不那么疯狂，并添加了注释。

// #include <bits/stdc++.h> is a bad choice. 
// This includes _EVERYTHING_ in C++, 
// but it only works in GCC afaik. For this particular 
// case we just need cout, so: 
#include <iostream>
// using the std namespace like this spills function calls like crazy in the global namespace. 
// it is both, conventient and "not too bad" (imho) in cpp files, 
// but never ever do this in .h files where it affects multiple cpp files. 
using namespace std;

void printRepeating(int arr[], int size)
{
// create a new array of size-2 and set to zero
int *count = new int[(size - 2)]{0};
int i;

cout << " Repeating elements are ";
// loop all elements
for(i = 0; i < size; i++)
{
int value = arr[i]; 
// increase the count for `value`
// note that if value<=0 or value>size-2, 
// then the program will crash! 
// the problem description is contrived, but it does 
// state that all values need to be >0 and <=size-2, 
// so this next array access is fine! 
count[value-1]++;
// we still have to subtract 1, because C arrays start 
// at index 0, but our problem description says we start at 1. 
// we could also create an array of size-1 and 
// "ignore" the first position in count[0] (it would never get used!)

// if the element appears the second time... 
if(count[value-1] == 2){
// then print it
cout << value << " ";
// btw: if you check with count[value-1]==2, then only
// the first duplicate is printed. 
// you could compare with count[value-1]>=2 then all 
// repeating elements are printed repeatetly. 
}
}
// free up the memory. we allocated with `new[]`
// so we also have to use `delete[]`
delete [] count; 
}

// Driver code
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
// next line is a standard trick. 
// a single int consumes 4bytes (typically), 
// the array will have size 7*4=28 bytes, so sizeof(arr)=28
// the first element is an int, so sizeof(arr[0]) = 4
// so sizeof(arr)/sizeof(arr[0]) = 7
// c and c++ don't have arr.length like java,etc., that's 
// why under certain circumstances this "trick" is used. 
int arr_size = sizeof(arr)/sizeof(arr[0]);
// call the function
printRepeating(arr, arr_size);
return 0;
}

// This is code is contributed by rathbhupendra. 
// Maybe fixed and annotated by hansi:)

---

我希望这能帮助你并回答一些问题。祝你的C++冒险好运！