How to Find the Largest Unique Number in Array (C++)?

  • 时间:2020-09-23 15:11:59
  • 分类:网络文摘
  • 阅读:104 次

Given an array of integers A, return the largest integer that only occurs once. If no integer occurs once, return -1.

Example 1:
Input: [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation:
The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it’s the answer.

Example 2:
Input: [9,9,8,8]
Output: -1

Explanation:
There is no number that occurs only once.

Note:
1 <= A.length <= 2000
0 <= A[i] <= 1000

Largest Unique Number: Sort and Check

You can sort the numbers and that will cost you O(nlogn) complexity. Once the array is sorted, you can skip the duplicate numbers easily by checking the value at the next index and the previous index. To avoid boundary checks, two values (INT_MIN and INT_MAX) are pushed to the front and the rear of the array respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        // push dummy values at front and end
        // to avoid boundary checks
        A.push_back(INT_MAX);
        A.push_back(INT_MIN);
        sort(begin(A), end(A));
        for (int i = A.size() - 2; i > 0; -- i) {
            if (A[i] == A[i - 1]) continue;
            if (A[i] == A[i + 1]) continue;
            return A[i];
        }
        return -1;
    }
};
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        // push dummy values at front and end
        // to avoid boundary checks
        A.push_back(INT_MAX);
        A.push_back(INT_MIN);
        sort(begin(A), end(A));
        for (int i = A.size() - 2; i > 0; -- i) {
            if (A[i] == A[i - 1]) continue;
            if (A[i] == A[i + 1]) continue;
            return A[i];
        }
        return -1;
    }
};

This algorithm uses constant space O(1).

Bucket Counting: Return the Largest Unique Number in O(N)

As the inputs are tightly constrainted to integers from 0 to 1000, we can have a O(1) 1001 buckets and do the counting in O(N) time. Once finished, we can start from 1000 and check downwards in O(1) time, return the largest unique number if it only appears once.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        int c[1001] = { 0 };
        for (const auto &n: A) {
            c[n] ++;
        }
        for (int i = 1000; i >= 0; -- i) {
            if (c[i] == 1) return i;
        }
        return -1;
    }
};
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        int c[1001] = { 0 };
        for (const auto &n: A) {
            c[n] ++;
        }
        for (int i = 1000; i >= 0; -- i) {
            if (c[i] == 1) return i;
        }
        return -1;
    }
};

The algorithm uses constant space and only require O(N) time.

Using Multiset to Count the Numbers

To generalise the solution, we can use a multiset (or a hash map) to do the counting. However, this needs two scans: the first scan will record the numbers in the multi-set or hash map and the second round, each non-qualified number (duplicate) will be skipped. And we can easily obtain a maximum from the rest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        unordered_multiset<int> dup;
        int ans = -1;
        for (const auto &n: A) {
            dup.insert(n);
        }
        for (const auto &n: A) {
            if (dup.count(n) == 1) {
                ans = max(ans, n);
            }
        }        
        return ans;
    }
};
class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        unordered_multiset<int> dup;
        int ans = -1;
        for (const auto &n: A) {
            dup.insert(n);
        }
        for (const auto &n: A) {
            if (dup.count(n) == 1) {
                ans = max(ans, n);
            }
        }        
        return ans;
    }
};

The time complexity is O(N) and the space complexity is also O(N).

You can use the Functional Programming to solve this problem: How to Find the Largest Unique Number in Array using Javascript (Functional Programming), or in Python: Python Method to Find the Largest Unique Number in an Array

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
美味在眼前,我手煮我心  离殇  数学题:若用a型箱,正好要装800箱  数学题:神舟五号飞行轨道的近地点高度为200km  数学题:汽车在途中停了一小时,客车速度比汽车慢  数学题:东西南北两条路交叉成直角  数学题:哥哥和弟弟进行100米赛跑  数学题:把14分成若干个自然数的和  数学题:张王李赵刘5人合作完成一项工程  数学题:姐姐8年后的年龄是妹妹3年前的5倍 
评论列表
添加评论