[Swift]LeetCode1093. 大样本统计 | Statistics from a Large Sample

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode

➤原文地址：https://www.cnblogs.com/strengthen/p/11032157.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

The middle element, if the elements of the sample were sorted and the number of elements is odd;
The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 意味着采样的整数为 k。

我们以浮点数数组的形式，分别返回样本的最小值、最大值、平均值、中位数和众数。其中，众数是保证唯一的。

我们先来回顾一下中位数的知识：

如果样本中的元素有序，并且元素数量为奇数时，中位数为最中间的那个元素；
如果样本中的元素有序，并且元素数量为偶数时，中位数为中间的两个元素的平均值。

示例 1：

输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]

示例 2：

输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,4.00000,2.18182,2.00000,1.00000]

提示：

count.length == 256
1 <= sum(count) <= 10^9
计数表示的众数是唯一的
答案与真实值误差在 10^-5 以内就会被视为正确答案

20ms

 1 class Solution {
 2     func sampleStats(_ count: [Int]) -> [Double] {
 3         guard count.count == 256 else { 
 4             assert(1 == 0, "Input error") 
 5         }
 6         var result = [Double]()
 7         var left = 0
 8         var right = 255
 9         while left <= 255 && count[left] == 0 {
10             left += 1
11         }
12         
13         while right > left && count[right] == 0 {
14             right -= 1
15         }
16         
17         result.append(Double(left))
18         result.append(Double(right))
19         
20         var counter = 0
21         var sum = 0
22         var mode = 0
23         var modeCounter = 0
24         for i in count.indices {
25             if count[i] > modeCounter {
26                 modeCounter = count[i]
27                 mode = i
28             }
29             counter += count[i]
30             sum += i * count[i]
31         }
32         result.append(Double(sum) / Double(counter))
33         
34         var start = counter % 2 != 0 ? counter / 2 + 1 : counter / 2
35         for i in 0..<count.count {
36             if start - count[i] > 0 {
37                 // print(start)
38                 // print(i)
39                 start -= count[i]
40                 continue
41             }
42             
43             if counter % 2 != 0 {
44                 result.append(Double(i))
45                 break
46             } else {
47                 if start - count[i] == 0 {
48                     var curr = i + 1
49                     
50                     while curr <= 255 && count[curr] == 0 {
51                         curr += 1
52                     } 
53                     result.append(Double(curr + i) / Double(2))
54                     break
55                 } else if start - count[i] < 0 {
56                     result.append(Double(i))
57                     break
58                 } 
59             }
60         }
61 
62         result.append(Double(mode))
63         return result
64     }
65 }

Runtime: 24 ms

Memory Usage: 21.2 MB

 1 class Solution {
 2     func sampleStats(_ count: [Int]) -> [Double] {
 3         var L:Int = 0
 4         var R:Int = 255
 5         while(L < 256 && count[L] == 0)
 6         {
 7             L += 1
 8         }
 9         while(L >= 0 && count[R] == 0)
10         {
11             R -= 1
12         }
13         let n:Int = count.reduce(0,+)
14         var sum:Double = 0
15         for i in 0...255
16         {
17             sum += Double(i * count[i])
18         }
19         let ave:Double = sum / Double(n)
20         var cur:Int = 0
21         var mid:Double = 0
22         if (n & 1) != 0
23         {
24             cur = 0
25             for i in 0...255
26             {
27                 cur += count[i]
28                 if cur >= (n + 1) / 2
29                 {
30                     mid = Double(i)
31                     break
32                 }
33             }
34         }
35         else
36         {
37             let x:Int = n / 2
38             let y:Int = x + 1
39             cur = 0
40             for i in 0...255
41             {
42                 cur += count[i]
43                 if cur >= x
44                 {
45                     mid += Double(i)
46                     break
47                 }
48             }
49             cur = 0
50             for i in 0...255
51             {
52                 cur += count[i]
53                 if cur >= y
54                 {
55                     mid += Double(i)
56                     break
57                 }
58             }
59             mid /= 2
60         }
61         let max_freq:Int = count.max() ?? Int.max
62         var mode:Double = -1.0
63         for i in 0...255
64         {
65             if count[i] == max_freq
66             {
67                 mode = Double(i)
68             }
69         }
70         return [Double(L), Double(R), ave, mid, mode]
71     }
72 }

36ms

 1 class Solution {
 2   func sampleStats(_ count: [Int]) -> [Double] {
 3     var minN = Int.max
 4     var maxN = Int.min
 5     var median: Double = 0
 6     var mode = 0
 7     var modeVal = 0
 8     var countOfNum = 0
 9     var sumVal = 0
10     for pair in count.enumerated() {
11       if pair.element != 0 {
12         minN = min(minN, pair.offset)
13         maxN = max(maxN, pair.offset)
14         if pair.element > mode {
15           mode = pair.element
16           modeVal = pair.offset
17         }
18         sumVal += pair.offset * pair.element
19         countOfNum += pair.element
20       }
21     }
22     
23     if countOfNum % 2 == 1 {
24       median = Double(valueBy(index: countOfNum/2, a: count))
25     } else {
26       median = Double(valueBy(index: countOfNum/2, a: count) + valueBy(index: countOfNum/2 - 1, a: count))/2
27     }
28     
29     return [Double(minN), Double(maxN), Double(sumVal)/Double(countOfNum), median, Double(modeVal)]
30   }
31   
32   func valueBy(index: Int, a: [Int]) -> Int {
33     var curentIndex = 0
34     for pair in a.enumerated() {
35       curentIndex += pair.element
36       if curentIndex > index {
37         return pair.offset
38       }
39     }
40     fatalError()
41   }
42 }