Title Description

Given an array of integers of even length arr, Only for arr After restructuring, we can meet “ For each 0 <= i < len(arr) / 2, There are arr[2 * i + 1] = 2 * arr[2 * i]” when , return true; otherwise , return false.

Example 1

 Input ：arr = [3,1,3,6]
 Output ：false

Example 2

 Input ：arr = [2,1,2,6]
 Output ：false

Example 3

 Input ：arr = [4,-2,2,-4]
 Output ：true
 explain ： It can be used  [-2,-4]  and  [2,4]  These two groups are made up of  [-2,-4,2,4]  or  [2,4,-2,-4]

• 0 <= arr.length <= 3 * 104
• arr.length It's even
• -105 <= arr[i] <= 105

Knowledge points involved ： Hashtable greedy Array Sort

Ideas

      It's actually a matching problem , First, the elements in the vector and the number of times they appear are stored in the hash table map in , Sort the elements in the vector and then traverse , Judge each number （ Even number ） Whether it can be successfully combined with twice its number or half its number , Current number is less than 0 The explanation is not enough , It can't be combined ,（ Odd numbers only need to be judged Whether this number and its double number can be successfully combined ）; Finally, traverse it again , Check all in the hash table key Corresponding value （ The number of times the corresponding element appears ） Is it all for 0, Once not for 0 Express , Combination failed , return false.

bool canReorderDoubled(vector<int>& arr) {
    
	unordered_map<int,int> count;
	for(int x:arr)
		count[x]++;
	sort(arr.begin(),arr.end());// Sort   Avoid excessive span , Cause confusion and error in matching 
	for(int i=0;i<arr.size();i++){
    
		if(arr[i]%2==0 && count[arr[i]] && count[arr[i]/2])// Even number , Judge whether half of the number can be combined with him 
		{
    
			count[arr[i]]--;
			count[arr[i]/2]--;
		}
		else if(arr[i]%2==0 && count[arr[i]] && count[2*arr[i]])// Even number , Judge the number of 2 Whether the number of times can be combined with him 
		{
    
			count[arr[i]]--;
			count[2*arr[i]]--;
		}
		else  if(arr[i]%2==1 && count[arr[i]] && count[2*arr[i]])// Odd hour , Judge the number of 2 Whether the number of times can be combined with him 
		{
    
			count[arr[i]]--;
			count[2*arr[i]]--;
		}
	}
	for(int x:arr)
		if(count[x]>0)// Indicates that the combination failed 
			return 0;
	return 1;
}