A test [2,2,2,1]. Who can tell me that solution's T(n)?


  • 0
    C
    void adjust(int *nums, int numsSize, int i)
    {
    	int j = i * 2 + 1;
    	int key = nums[i];
    	while (j < numsSize) {
    		if (j + 1 < numsSize && nums[j + 1] > nums[j])
    			j++;
    		if (key < nums[j]) {
    			nums[i] = nums[j];
    			i = j;
    			j = i * 2 + 1;
    		}
    		else
    			break;
    	}
    	nums[i] = key;
    }
    int thirdMax(int* nums, int numsSize) {
    	int i, count, tmp = INT_MAX, max;
    	for (i = (numsSize - 2)/2; i >= 0; i--)
    		adjust(nums, numsSize, i);
    	max = nums[0];
    	for (count = 0; numsSize > 1; numsSize--) {
    		if (tmp != nums[0])
    			count++;
    		tmp = nums[0];
    		nums[0] = nums[numsSize - 1];
    		adjust(nums, numsSize - 1, 0);
    		if (count == 2)
    			break;
    	}
    	if (count == 2)
    		max = nums[0];
    	return max;
    }
    

Log in to reply
 

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