本站首页 返回顶部 关于博主

(4/500)从有限范围的数组中找出重复元素

PDF版

给定一个数组,它有n个元素,数组中包含1到n-1这些值。在这个数组中,除了一个元素是重复的,其他元素都只出现了一次。请找出重复的元素。

例如,
输入: { 1, 2, 3, 4, 4 }
输出:The duplicate element is 4

输入:{ 1, 2, 3, 4, 2 }
输出:The duplicate element is 2

 

1. 通过Hash来计算

这种算法的思想是使用Hash来解决问题。在这个算法中,我们使用了一个辅助数组,数组中的元素是boolean类型,数组中元素的值用以表示某个值是否出现过。如果出现过,那么就返回true。
C++语言实现:


#include
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
// create an visited array of size n+1
// we can also use map instead of visited array
bool visited[n];
fill(visited, visited + n, 0); // sets every value in the array to 0

// for each element of the array mark it as visited and
// return the element if it is seen before
for (int i = 0; i < n; i++) { // if element is seen before if (visited[arr[i]]) return arr[i]; // mark element as visited visited[arr[i]] = true; } // no duplicate found return -1; } // main function int main() { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Duplicate element is " << findDuplicate(arr, n); return 0; } [/cpp] Java语言实现: [java] class findDuplicate { // Function to find a duplicate element in a limited range array public static int findDuplicate(int arr[]) { // n is length of the array int n = arr.length; // create an visited array of size n+1 // we can also use map instead of visited array boolean visited[] = new boolean[n + 1]; // for each element of the array mark it as visited and // return the element if it is seen before for (int i = 0; i < n; i++) { // if element is seen before if (visited[arr[i]]) return arr[i]; // mark element as visited visited[arr[i]] = true; } // no duplicate found return -1; } // main function public static void main (String[] args) { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 4 }; System.out.println("Duplicate element is " + findDuplicate(arr)); } } [/java]
输出: Duplicate element is 4

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(n)。

 

2

我们还能使用常量空间(空间复杂度为O(n))解决问题。既然数组中除了一个元素是重复之外,其他元素都是唯一的,并且元素的值在1到n-1之间,我们可以把数组的下标作为key,把元素取负数来判断元素是否重复。例如,队员每个元素arr[i],我们得到它的绝对值abs(arr[i]),并修改下标为abs(arr[i]) – 1的这个元素的正负号。最后,我们再遍历一次数组,如果第 i 个元素的值是正数,那么重复的元素就是 i + 1。

上面的算法我们遍历了2次数组。其实,我们可以缩为1次。对于每一个元素arr[i],我们得到绝对值abs(arr[i]),然后反转第abs(arr[i])-1个元素的符号,如果准备反转符号的元素已经是负数了,那么它一定是那个重复的数字。

C++语言实现:


#include
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
int duplicate = -1;

// do for each element in the array
for (int i = 0; i < n; i++) { // get absolute value of current element int absVal = (arr[i] < 0) ? -arr[i] : arr[i]; // make element at index abs(arr[i])-1 negative if it is positive if (arr[absVal - 1] >= 0)
arr[absVal – 1] = -arr[absVal – 1];
else
{
// if element is already negative, it is repeated
duplicate = absVal;
break;
}
}

// restore original array before returning
for (int i = 0; i < n; i++) { // make negative elements positive if (arr[i] < 0) arr[i] = -arr[i]; } // return duplicate element return duplicate; } // main function int main() { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Duplicate element is " << findDuplicate(arr, n); return 0; } [/cpp] java语言实现: [java] class findDuplicate { // Function to find a duplicate element in a limited range array public static int findDuplicate(int arr[]) { // n is length of the array int n = arr.length; int duplicate = -1; // do for each element in the array for (int i = 0; i < n; i++) { // get absolute value of current element int absVal = (arr[i] < 0) ? -arr[i] : arr[i]; // make element at index abs(arr[i]) - 1 negative // if it is positive if (arr[absVal - 1] >= 0)
arr[absVal – 1] = -arr[absVal – 1];
else
{
// if element is already negative, it is repeated
duplicate = absVal;
break;
}
}

// restore original array before returning
for (int i = 0; i < n; i++) { // make negative elements positive if (arr[i] < 0) arr[i] = -arr[i]; } // return duplicate element return duplicate; } // main function public static void main (String[] args) { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 4 }; System.out.println("Duplicate element is " + findDuplicate(arr)); } } [/java] 输出: Duplicate element is 2

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 使用异或

我们还可以使用异或(XOR)来解决问题。思路就是把所有的元素和1到n-1的数都异或一次,由于a^a = 0, 0^0 = 0,a^0 = a。在这个异或中,所有的元素都出现了2次,而重复的元素出现了3次,所以最后的值就是重复的元素。

C++语言实现:


#include
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int A[], int n)
{
int XOR = 0;

// take xor of all array elements
for (int i = 0; i < n; i++) XOR ^= A[i]; // take xor of numbers from 1 to n-1 for (int i = 1; i <= n-1; i++) XOR ^= i; // same elements will cancel out each other as a ^ a = 0, // 0 ^ 0 = 0 and a ^ 0 = a // xor will contain the missing number return XOR; } // main function int main() { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Duplicate element is " << findDuplicate(arr, n); return 0; } [/cpp] java语言实现: [java] class findDuplicate { // Function to find a duplicate element in a limited range array public static int findDuplicate(int A[]) { // n is length of the array int n = A.length; int XOR = 0; // take xor of all array elements for (int i = 0; i < n; i++) XOR ^= A[i]; // take xor of numbers from 1 to n-1 for (int i = 1; i <= n - 1; i++) XOR ^= i; // same elements will cancel out each other as a ^ a = 0, // 0 ^ 0 = 0 and a ^ 0 = a // xor will contain the missing number return XOR; } // main function public static void main (String[] args) { // input array contains n numbers between [1 to n - 1] // with one duplicate int arr[] = { 1, 2, 3, 4, 4 }; System.out.println("Duplicate element is " + findDuplicate(arr)); } } [/java] 输出: Duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。

 

4.求和

最后,我们可以通过求和的方式解决问题:先计算出所有元素的和,然后再减去1到n-1的和,最后的值就是重复的数。简单吧。:)

C++语言:


#include
#include
#include

template
int find_duplicate(It start, It finish)
{
auto size = std::distance(start, finish);

int actual_sum = std::accumulate(start, finish, 0);
int expected_sum = size * (size – 1) / 2;

return actual_sum – expected_sum;
}

int main()
{
std::array arr1 = {{ 1, 2, 3, 4, 4 }};
std::array arr2 = {{ 1, 2, 3, 4, 2 }};

std::cout << "The duplicate element is " << find_duplicate(arr1.begin(), arr1.end()) << '\n'; std::cout << "The duplicate element is " << find_duplicate(arr2.begin(), arr2.end()) << '\n'; } [/cpp] 输出:

The duplicate element is 4
The duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。




请你留言