Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1287.html

1287. Element Appearing More Than 25% In Sorted Array (Easy)

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

 

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

 

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

Related Topics:
Array

Solution 1.

• Java
• C++
• Python
• Go
• Javascript
• Php

• class Solution {
      public int findSpecialInteger(int[] arr) {
          int length = arr.length;
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          for (int i = 0; i < length; i++) {
              int num = arr[i];
              int count = map.getOrDefault(num, 0);
              count++;
              if (count * 4 > length)
                  return num;
              map.put(num, count);
          }
          return 0;
      }
  }
  
  ############
  
  class Solution {
      public int findSpecialInteger(int[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; ++i) {
              if (arr[i] == arr[i + (n >> 2)]) {
                  return arr[i];
              }
          }
          return 0;
      }
  }
  

• // OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int findSpecialInteger(vector<int>& A) {
          int start = 0, N = A.size();
          for (int i = 1; i < N; ) {
              while (i < N && A[i] == A[start]) ++i;
              if (i - start > N / 4) return A[start];
              start = i;
          }
          return A[0];
      }
  };
  

• class Solution:
      def findSpecialInteger(self, arr: List[int]) -> int:
          n = len(arr)
          for i, val in enumerate(arr):
              if val == arr[i + (n >> 2)]:
                  return val
          return 0
  
  ############
  
  # 1287. Element Appearing More Than 25% In Sorted Array
  # https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
  
  class Solution:
      def findSpecialInteger(self, arr: List[int]) -> int:
          n = len(arr)
          m = len(arr) // 4
          
          for i in range(n-m+1):
              if arr[i] == arr[i+m]:
                  return arr[i]
  

• func findSpecialInteger(arr []int) int {
  	n := len(arr)
  	for i, val := range arr {
  		if val == arr[i+(n>>2)] {
  			return val
  		}
  	}
  	return 0
  }
  

• /**
   * @param {number[]} arr
   * @return {number}
   */
  var findSpecialInteger = function (arr) {
      const n = arr.length;
      for (let i = 0; i < n; ++i) {
          if (arr[i] == arr[i + (n >> 2)]) {
              return arr[i];
          }
      }
      return 0;
  };
  
  

• class Solution {
      /**
       * @param Integer[] $arr
       * @return Integer
       */
      function findSpecialInteger($arr) {
          $len = count($arr);
          for ($i = 0; $i < $len; $i++) {
              if ($arr[$i] == $arr[$i + ($len >> 2)]) return $arr[$i];
          }
          return -1;
      }
  }
  

All Problems

All Solutions