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

(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 <iostream>
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</iostream></p>
  // for each element of the array mark it as visited and
  // return the element if it is seen before
  for (int i = 0; i &lt; 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 &lt;&lt; "Duplicate element is " &lt;&lt; findDuplicate(arr, n); 
  return 0; 
} 
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)); 
 } 
} 
输出: 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 <iostream>
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 &lt; n; i++) { 
    // get absolute value of current element 
    int absVal = (arr[i] &lt; 0) ? -arr[i] : arr[i]; 
    // make element at index abs(arr[i])-1 negative if it is positive 
    if (arr[absVal - 1] &gt;= 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 &lt; n; i++) { 
    // make negative elements positive 
    if (arr[i] &lt; 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 &lt;&lt; "Duplicate element is " &lt;&lt; findDuplicate(arr, n); 
  return 0; 
}
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)); 
  } 
} 
输出: Duplicate element is 2

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

 

3. 使用异或

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


java语言实现
public int findDuplicate(int arr[]) {
	int size = arr.length;
	// int 会存在越界的情况,所以要转换成 long
	// long 一定不会越界
	long expected_sum = ((long) size) * (size - 1) / 2;
	long actual_sum = 0;

	for (int i = 0; i < size; i++) {
		actual_sum += arr[i];
	}
	return (int) (actual_sum - expected_sum);
}
输出: Duplicate element is 2

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

 

4.求和

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

代码略。
输出:

The duplicate element is 4
The duplicate element is 2

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

备注:本文为初始版本,在《算法题:有限范围的数组中找出重复元素》中重新整理,进一步完善,提供更多的算法。




请你留言

Protected with IP Blacklist CloudIP Blacklist Cloud