414. The third largest number AND 611

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

414. The third largest number

Given a non-empty array, return the third largest number in the array. If not, return the largest number in the array.

Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third largest number is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third largest number does not exist, so return the largest number 2. Example 3: Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third largest number required to return is the third largest number among all the different numbers. There are two numbers with a value of 2 in this example, and they are both second. The third largest number of all the different numbers is 1.Copy the code

Their thinking

Maintain three variables that represent numbers one, two, and three

When num is greater than the largest number, move the first and second digits back
When num is greater than the second largest number, the original second number is moved back
When num is greater than the third largest number, the value is assigned to the third largest number

code

class Solution {
    public int thirdMax(int[] nums) {

        Integer first=null,sec=null,third=null;
        for (int num : nums) {
            if(first! =null&&num==first||sec! =null&&num==sec||third! =null&&num==third)
                continue;
            if(first==null||num>first)
            {
                third=sec;
                sec=first;
                first=num;
            }else if (sec==null||num>sec){
                third=sec;
                sec=num;
            }else if (third==null||num>third)
                third=num;
        }
        return third==null?first:third;

    }
}
Copy the code

611. Number of valid triangles

Given an array of non-negative integers, your task is to count the number of triples that can form the three sides of a triangle.

Example 1:

Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3Copy the code

Note:

The length of the array cannot exceed 1000.
The integer range in the array is [0, 1000].

Their thinking

First sort the array from small to large, fix one edge I, and traverse the other edge J. We find that when J keeps growing, our third edge can also continue to grow on the original basis, so we only need to maintain the pointer K of the third edge

code

class Solution {
    public int triangleNumber(int[] nums) {

        Arrays.sort(nums);
        int n=nums.length,res=0;
        for(int i=0; i<n; i++) {int k=i;
            for (int j=i+1; j<n; j++) {while (k+1<n&&nums[k+1]<nums[i]+nums[j])
                    k++;
                res+= Math.max(0,k-j); }}returnres; }}Copy the code

414. The third largest number AND 611