Leetcode 1968. Construct an array whose elements are not equal to the average value of two adjacent elements (yes, finally solved)

To give you one Subscript from 0 Start Array of nums , The array consists of several Different from each other Integer composition . You're going to rearrange the elements in the array to meet ： After rearranging , Every element in the array is It's not equal to Of adjacent elements on both sides Average .

A more formulaic statement is , The rearranged array should satisfy this property ： For scope 1 <= i < nums.length - 1 Each of the i ,(nums[i-1] + nums[i+1]) / 2 It's not equal to nums[i] All set up .

Return any rearrangement result that meets the meaning of the question .

Example 1：

 Input ：nums = [1,2,3,4,5]
 Output ：[1,2,4,5,3]
 explain ：
i=1, nums[i] = 2,  The average value of two adjacent elements is  (1+4) / 2 = 2.5
i=2, nums[i] = 4,  The average value of two adjacent elements is  (2+5) / 2 = 3.5
i=3, nums[i] = 5,  The average value of two adjacent elements is  (4+3) / 2 = 3.5

Example 2：

 Input ：nums = [6,2,0,9,7]
 Output ：[9,7,6,2,0]
 explain ：
i=1, nums[i] = 7,  The average value of two adjacent elements is  (9+6) / 2 = 7.5
i=2, nums[i] = 6,  The average value of two adjacent elements is  (7+2) / 2 = 4.5
i=3, nums[i] = 2,  The average value of two adjacent elements is  (6+0) / 2 = 3

Tips ：

• 3 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

Main idea ：
What I'm thinking about here is , Two big ones and one small one , The so-called "two big and one small" is to add a big element first , Then add a small element , Add another big element , So you can sort the elements first and add them to the new array according to this idea （ In fact, it is the swing sequence that can be solved ）

Code:

class Solution {
    
public:
    vector<int> rearrangeArray(vector<int>& nums) {
    
        
        sort(nums.begin(),nums.end());
        vector<int>res;
        int end=nums.size();
        int start=0;
        for(int i=0;i<nums.size();i++)
        {
    
            if((i%2)==0)
            {
    
                res.push_back(nums[--end]);
            }
            else
                res.push_back(nums[start++]);
            
            
        }
        return res;
        
    }
};