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

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

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) —

推荐阅读:
健康饮食:人们都说吃了“隔夜菜”致癌,这是真的吗?  豆腐味美又养生,做一道家常菜让你胃口大开  女性在特殊时期饮食需要注意,不能吃这些食物  此菜肴脆嫩爽口肉香浓郁且色香味俱全,为冬季百吃不厌的佳肴  枸杞子吃法正确才能更好吸收营养,但人在出现状况时最好别吃它  土豆是一种非常普通的蔬菜,但其营养保健价值令人难以置信  大家别忘了喝碗营养丰富的腊八粥,它对女性朋友的好处尤其多  经常吃一点柚子好处多,柚子皮的作用也不少,以后别再浪费啦  牛奶是常见的营养饮品,如果选择不对,既浪费钱还影响健康  香蕉对身体健康有很多好处,教你用香蕉做一道美味粥吧 
评论列表
添加评论