Array Partitioning I


  • 0

    Click here to see the full article post


  • 0

    Hi, the sorting way is accepted actually.


  • 0
    D

    Why I can't search this problem in leetcode ?


  • 0
    D

    I think so~~the sorting way is accepted..
    And the second method is actually counting sort.. Am I right?


  • 0

    my sorting solution got AC and the judge said it beats 100% of the other java solutions...


  • 0
    S

    The sorting method was accepted for my case too


  • 0
    S

    Generally speaking, If sort takes O(nlogn) time complexity, it also takes O(logn) space.


  • 0

    My sorting solution is also ACed.


  • 0
    R

    My answer is the same as Approach #2


  • 0
    1

    class Solution {
    public:
    int arrayPairSum(vector<int>& nums)
    {
    int n = nums.size();
    int max = 0;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n - 1; i = i + 2)
    {
    max += nums[i];
    }
    return max;
    }
    };


  • 0
    K

    class Solution(object):
    def arrayPairSum(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    n = 0
    res = 0
    while n < len(nums):
    res += nums[n]
    n += 2

        return res

  • 0
    G

    class Solution {
    public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;
    for(int i=0;i<nums.length;i=i+2) {
    sum = sum + Math.min(nums[i], nums[i+1]);
    }
    return sum;
    }
    }


  • 0
    A

    Solution in C

    /*
     * main.c
     *
     *  Created on: Sep 2, 2017
     *      Author: Prakhar Avasthi
     */
    
    /*
     * This problem is pretty straightforward, as in this problem we need to make
     * n pairs each with 2 numbers from 2n numbers such that sum of min of two numbers
     * in each pair is largest.
     * basically if we sort the array and sum every odd digit, we will have our answer.
     * Problem is easy, I would suggest you to try various sorting algorithm.
     * I tried merge sort. In merge sort, there are 2 steps:
     * 1. divide array in 2 parts recursively as we need to implement merging in bottom-up fashion
     * 2. while merging bottom-up, we will get/make 2 sorted arrays, using some extra space
     * we will merge two sorted arrays in 1 extra space array and copy back.
     * Here 2 sorted arrays doesn't mean that we will have two actual array,
     * we will have one array but we will know two start points and two end points.
     * After sorting, a simple loop will fetch the accepted answer.
     * */
    
    #include<stdio.h>
    #include<stdlib.h>
    
    void merge(int* arr, int start, int mid, int end)
    {
    	int p = start, q = mid+1;
    	int *temp_arr;
    	temp_arr = (int *)malloc((end+1)*sizeof(int));
    	int i=start;
    
    	while(p<mid+1 && q<end+1)
    	{
    		if(arr[p]<=arr[q])
    		{
    			temp_arr[i] = arr[p];
    			i++; p++;
    		} else {
    			temp_arr[i] = arr[q];
    			i++; q++;
    		}
    	}
    
    	if(p<=mid)
    	{
    		while(p<=mid)
    			temp_arr[i++] = arr[p++];
    	}
    
    	if(q<=end)
    	{
    		while(q<=end)
    			temp_arr[i++] = arr[q++];
    	}
    	for(int j = start; j<=end; j++)
    		arr[j] = temp_arr[j];
    	free(temp_arr);
    }
    
    void merge_sort(int *arr, int left, int right)
    {
    	if(left == right) return;
    
    	int new_right = (left+right)/2;
    	merge_sort(arr, left, new_right);
    	merge_sort(arr, new_right+1, right);
    	merge(arr, left, new_right, right);
    }
    
    int arrayPairSum(int* nums, int numsSize) {
    	int result = 0;
    
    	merge_sort(nums, 0, numsSize-1);
    
    	for(int i = 0; i < numsSize; i=i+1)
    	{
    		printf("%d ",nums[i]);
    		result = result + nums[i];
    	}
    	return result;
    }
    
    int main()
    {
    	int arr[10] = {1,-3,5,-4,8,9,-2,0,7,6};
    
    	setbuf(stdout, NULL);
    
    	printf("%d", arrayPairSum(arr,10));
    	return 0;
    }
    
    
    

  • 0
    G

    Solution in Python

    class Solution(object):
        def arrayPairSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            nums.sort()                
            return sum(nums[::2])
    

  • 0
    Z

    class Solution {
    public int arrayPairSum(int[] nums) {
    int len=nums.length;
    Arrays.sort(nums);
    int sum=0;
    for(int i=0;i<len/2;i++){
    sum+=nums[2*i];
    }
    return sum;
    }
    }


  • 0
    K

    class Solution {
    public:
    int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int min=0,output =0;
    for(int i=0;i<nums.size();i+=2)
    {

            int x = nums[i];
            
            output += x;
        }
        return output;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.