Մեծամասնության առաջնորդ Մուրի քվեարկության ալգորիթմով:

Մարտահրավերի նկարագրություն

Հաշվի առնելով nums զանգվածը՝ n, վերադարձրեք մեծամասնության տարրը:

Մեծամասնության տարրը այն տարրն է, որը հայտնվում է ավելի քան ⌊n / 2⌋ անգամ: Դուք կարող եք ենթադրել, որ մեծամասնության տարրը միշտ գոյություն ունի զանգվածում:

Օրինակ 1

Input: nums = [3,2,3]
Output: 3

Օրինակ 2

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Մոտեցում 1. Տեսակավորում

Ինտուիցիա՝

Այս մոտեցման հիմքում ընկած ինտուիցիան այն է, որ եթե տարրը զանգվածում հայտնվում է ավելի քան n/2 անգամ (որտեղ n-ը զանգվածի չափն է), այն միշտ կզբաղեցնի միջին դիրքը, երբ զանգվածը տեսակավորվում է: Հետևաբար, մենք կարող ենք տեսակավորել զանգվածը և տարրը վերադարձնել n/2 ինդեքսում։

Բացատրություն.

1. Կոդը սկսվում է nums զանգվածը չնվազող կարգով դասավորելով՝ օգտագործելով Typescript ստանդարտ գրադարանի sort ֆունկցիան: Սա վերադասավորում է տարրերն այնպես, որ նույնական տարրերը խմբավորվեն միասին:
2. Զանգվածը տեսակավորելուց հետո մեծամասնության տարրը միշտ ներկա կլինի n/2 ինդեքսում, որտեղ n զանգվածի չափն է:

• Դա պայմանավորված է նրանով, որ մեծամասնության տարրը հանդիպում է ավելի քան n/2 անգամ, և երբ զանգվածը տեսակավորվում է, այն կզբաղեցնի միջին դիրքը։

3. Կոդը վերադարձնում է n/2 ինդեքսում գտնվող տարրը որպես մեծամասնության տարր:

Այս մոտեցման ժամանակային բարդությունը O(n log n) է, քանի որ n չափի զանգվածի տեսակավորումը պահանջում է O(n log n) ժամանակ:

function majorityElement(nums: number[]): number {
  nums.sort((a, b) => a - b); // Sort the array in ascending order
  const n: number = nums.length;
  return nums[Math.floor(n / 2)];
}

Մոտեցում 2. Հեշ քարտեզ

Ինտուիցիա.

Հեշ-քարտեզ օգտագործելու հիմքում ընկած ինտուիցիան զանգվածի յուրաքանչյուր տարրի դեպքերը հաշվելն է և այնուհետև բացահայտել այն տարրը, որը հանդիպում է ավելի քան n/2 անգամ: Հաշիվները պահելով հեշ քարտեզում, մենք կարող ենք արդյունավետ կերպով հետևել յուրաքանչյուր տարրի երևույթներին:

Բացատրություն.

Իհարկե, եկեք բաժանենք TypeScript ֆունկցիան majorityElement(nums: number[]): number | null քայլ առ քայլ.

1. const n: number = nums.length;. Այս տողը հայտարարում է n հաստատուն, որը պահպանում է nums մուտքային զանգվածի երկարությունը, որը ներկայացնում է զանգվածի տարրերի ընդհանուր թիվը:
2. const occurrences: Map<number, number> = new Map();. Այս տողը սկզբնավորում է դատարկ քարտեզը, որը կոչվում է occurrences: Այս Քարտեզում ստեղները թվեր են (տարրեր nums զանգվածից), իսկ արժեքները՝ դրանց համապատասխան երևույթները կամ հաշվումները:
3. for (let i = 0; i < n; i++) { ... }. Այս օղակը կրկնվում է nums զանգվածի յուրաքանչյուր տարրի միջով:
4. const num = nums[i];: Շրջանակի ներսում մենք հանում ենք զանգվածի ընթացիկ տարրը և այն պահում num փոփոխականում:
5. occurrences.set(num, (occurrences.get(num) || 0) + 1);. Այս տողը հաշվում է nums զանգվածում յուրաքանչյուր տարրի առաջացումը՝ օգտագործելով occurrences Քարտեզը: Եթե ​​num տարրն արդեն առկա է Քարտեզում, մենք առբերում ենք դրա ընթացիկ թիվը (օգտագործելով occurrences.get(num)), կամ եթե այն չկա (այսինքն՝ տարրն առաջին անգամ է հանդիպում), մենք օգտագործում ենք 0: Այնուհետև մենք ավելացնում ենք հաշվարկը 1-ով և այն նորից պահում Քարտեզում:
6. const threshold: number = n / 2;: Այստեղ մենք հաշվարկում ենք շեմային արժեքը՝ n զանգվածի տարրերի ընդհանուր թիվը բաժանելով 2-ի: .
7. for (const [key, value] of occurrences.entries()) { ... }. Այս օղակը կրկնվում է occurrences Քարտեզի յուրաքանչյուր մուտքի (բանալին-արժեք զույգ) միջով:
8. if (value > threshold) { ... }. Օղակի ներսում մենք ստուգում ենք, արդյոք value ընթացիկ տարրի հաշվարկը մեծ է շեմային արժեքից: Եթե ​​այդպես է, ապա ներկայիս key տարրը զանգվածի մեծամասնության տարրն է: Մենք անմիջապես վերադարձնում ենք այս տարրը որպես արդյունք:
9. Եթե ​​հանգույցն ավարտվում է առանց մեծամասնության տարր գտնելու, մենք հասնում ենք return null; // No majority element found տողին, ինչը նշանակում է, որ զանգվածում մեծամասնության տարր չկա: Նման դեպքերում ֆունկցիան վերադարձնում է null:

function majorityElement(nums: number[]): number | null {
  const n: number = nums.length;
  const occurrences: Map<number, number> = new Map();

  for (let i = 0; i < n; i++) {
    const num = nums[i];
    occurrences.set(num, (occurrences.get(num) || 0) + 1);
  }

  const threshold: number = n / 2;
  for (const [key, value] of occurrences.entries()) {
    if (value > threshold) {
      return key;
    }
  }

  return null; // No majority element found
}

Մոտեցում 3. Մուրի քվեարկության ալգորիթմ

Ինտուիցիա՝

Մուրի քվեարկության ալգորիթմի հիմքում ընկած ինտուիցիան հիմնված է այն փաստի վրա, որ եթե զանգվածում կա մեծամասնության տարր, այն միշտ կմնա առաջատարի դիրքում, նույնիսկ այլ տարրերի հետ հանդիպելուց հետո:

Բացատրություն.

Ալգորիթմ՝

1. Նախաձեռնեք երկու փոփոխական՝ count և candidate: Սահմանեք count-ը 0-ի, իսկ candidate-ը՝ կամայական արժեքի:
2. Կրկնել nums զանգվածի միջով:
   ա. Եթե ​​count-ը 0 է, ապա նշանակեք ընթացիկ տարրը որպես նոր candidate և ավելացրեք count 1-ով:
   բ. Եթե ​​ընթացիկ տարրը նույնն է, ինչ candidate-ը, ավելացրեք count 1-ով:
   գ. Եթե ​​ընթացիկ տարրը տարբերվում է candidate-ից, ապա count-ը նվազեցրեք 1-ով:
3. Կրկնելուց հետո candidate փոփոխականը կպահի մեծամասնության տարրը:

Բացատրություն.

1. Ալգորիթմը սկսվում է առաջին տարրը որպես մեծամասնական թեկնածու ընդունելով և հաշվարկը սահմանում է 1-ի:
2. Երբ այն կրկնվում է զանգվածի միջով, այն համեմատում է յուրաքանչյուր տարր թեկնածուի հետ.
   a. Եթե ​​ներկայիս տարրը համընկնում է թեկնածուի հետ, դա առաջարկում է, որ այն ամրապնդի մեծամասնության տարրը, քանի որ այն նորից հայտնվում է: Հետևաբար, հաշվարկն ավելանում է 1-ով:
   բ. Եթե ​​ներկայիս տարրը տարբերվում է թեկնածուից, ապա դա հուշում է, որ մեծամասնության տարրի և այլ տարրերի դեպքերը կարող են հավասար թվով լինել: Այսպիսով, հաշվարկը նվազում է 1-ով:

• Նկատի ունեցեք, որ քանակի նվազումը չի փոխում այն ​​փաստը, որ մեծամասնության տարրը տեղի է ունենում ավելի քան n/2 անգամ:

3. Եթե հաշվարկը դառնում է 0, նշանակում է, որ ներկայիս թեկնածուն այլևս մեծամասնության պոտենցիալ տարր չէ: Այս դեպքում մնացած տարրերից ընտրվում է նոր թեկնածու։

4. Ալգորիթմը շարունակում է այս գործընթացը այնքան ժամանակ, քանի դեռ չի անցել ամբողջ զանգվածը:

5. candidate փոփոխականի վերջնական արժեքը կպահի մեծամասնության տարրը:

Ճշտության բացատրություն.
Ալգորիթմն աշխատում է այն ենթադրության հիման վրա, որ մեծամասնության տարրը զանգվածում հանդիպում է ավելի քան n/2 անգամ: Այս ենթադրությունը երաշխավորում է, որ նույնիսկ եթե այլ տարրերի կողմից հաշվարկը զրոյացվի 0-ի, մեծամասնության տարրը ի վերջո կվերականգնի առաջատարը:

Դիտարկենք երկու դեպք.

1. Եթե ​​մեծամասնության տարրն ունի n/2-ից ավելի դեպքեր.

• Ալգորիթմը կապահովի, որ հաշվարկը դրական մնա մեծամասնության տարրի համար ողջ անցման ընթացքում՝ երաշխավորելով, որ այն կընտրվի որպես վերջնական թեկնածու:

2. Եթե մեծամասնության տարրը ունի ճշգրիտ n/2 երևույթ.

• Այս դեպքում մեծամասնության տարրի և մնացած տարրերի համար կլինեն հավասար թվով երևույթներ:
• Այնուամենայնիվ, մեծամասնության տարրը դեռ կընտրվի որպես վերջնական թեկնածու, քանի որ այն միշտ առաջատար է լինելու ցանկացած այլ տարրի նկատմամբ:

Երկու դեպքում էլ ալգորիթմը ճիշտ կբացահայտի մեծամասնության տարրը:

Մուրի քվեարկության ալգորիթմի ժամանակային բարդությունը O(n) է, քանի որ այն մեկ անգամ անցնում է զանգվածը:

Այս մոտեցումը արդյունավետ է տեսակավորման համեմատ, քանի որ այն պահանջում է միայն մեկ անցում զանգվածի միջով և չի փոխում տարրերի սկզբնական կարգը:

function majorityElement(nums: number[]): number | null {
  let count: number = 0;
  let candidate: number = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }

    if (num === candidate) {
      count++;
    } else {
      count--;
    }
  }

  // Now, 'candidate' contains the potential majority element.
  // Check if it appears more than n/2 times to ensure it's the majority element.
  count = 0;
  for (const num of nums) {
    if (num === candidate) {
      count++;
    }
  }

  return count > nums.length / 2 ? candidate : null;
}