easy C/C++ loop|| 1-line 3ms 96.18%||deque
Intuition\n Describe your first thoughts on how to solve this problem. \n1-loop with swap, C solution uses XOR to implement swap function!\nThis swap function i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1-loop with swap, C solution uses XOR to implement swap function!\nThis swap function is an old-school call-by-address function and does not use extra space! SWAP is a macro for a revised version using C.\n\n2nd approach is 1-line using sort w.r.t. ordering defined by lambda function.\n\n3rd approach uses deque which is also fast.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor fast implementation, it is possible to replace `nums[i]%2` by the bit operation `nums[i] & 1`!\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n)$ vs $O(n\\log n)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code\n```C []\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\nvoid swap(int *x, int *y){//Use C-pointers, XOR, no extra space\n    *x=(*x)^(*y);\n    *y=(*x)^(*y);\n    *x=(*x)^(*y);\n}\n#define SWAP(x, y)  {(x)^=(y); (y)=(x)^(y); (x)=(x)^(y);}\n\nint* sortArrayByParity(int* nums, int numsSize, int* returnSize){\n    int j=numsSize-1;\n    *returnSize=numsSize;\n    for(register int i=0; i<j; ){\n        if((nums[i]&1)==1 && (nums[j]&1)==0){\n        //    swap(&nums[i], &nums[j]);//Call by address\n            SWAP(nums[i], nums[j]);// using macro\n            i++, j--;\n        }\n        else{\n            if ((nums[i]&1)==0) i++;\n            if ((nums[j]&1)==1) j--;\n        } \n    }\n    return nums;\n}\n```\n```C++ []\n\nclass Solution {\npublic:\n    vector<int> sortArrayByParity(vector<int>& nums) {\n        int j=nums.size()-1;\n        for(int i=0; i<j; ){\n            if((nums[i]&1)==1 && (nums[j]&1)==0){\n                swap(nums[i], nums[j]);\n                i++, j--;\n            }\n            else{\n                if ((nums[i]&1)==0) i++;\n                if ((nums[j]&1)==1) j--;\n            } \n        }\n        return nums;\n    }\n};\n```\n# C++ 1-line 3ms Beats 96.18% though with slow TC\n```\nclass Solution {\npublic:\n    vector<int> sortArrayByParity(vector<int>& nums) {\n        sort(nums.begin(), nums.end(), [&](int x, int y){return (x&1)<(y&1);}); return nums;\n    }\n};\n```\n# C++ using deque TC: O(n) SC: O(n)\n```\nclass Solution {\npublic:\n    vector<int> sortArrayByParity(vector<int>& nums) {\n        deque<int> q;\n        for(int x: nums){\n            if((x&1)==1) \n                q.push_back(x);\n            else\n                q.push_front(x);     \n        }\n        return vector<int>(q.begin(), q.end());\n    }\n};\n```
['Two Pointers', 'Bit Manipulation', 'Queue', 'Sorting', 'C++']