Գտեք 1-ի առավելագույն թվով շարքը  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են 24 * 7 նորարարության լաբորատորիաներ Amazon Microsoft Paytm
Դասավորություն Matrix Որոնում

Խնդիրի հայտարարություն  

«Գտեք տողը առավելագույն թվով 1-ի հետ» խնդրում մենք տվել ենք ա matrix(2D զանգված), որը պարունակում է երկուական թվանշան `յուրաքանչյուր շարքում տեսակավորված: Գտեք այն տողը, որն ունի առավելագույն 1-ը:

Մուտքային ձևաչափ  

Երկու ամբողջական թվերի արժեքներ պարունակող առաջին տողը n, m:

Հաջորդը, n տողեր, որոնք պարունակում են m տարածությամբ առանձնացված ամբողջ թվեր (0 կամ 1):

Արդյունքի ձևաչափ  

Առաջին և միայն մեկ տող, որը պարունակում է 1-ի առավելագույն թիվ ունեցող տող նշող ամբողջ թիվ:

Խոչընդոտները  

  • 1 <= n, m <= 10 ^ 3
  • 0 <= a [i] [j] <= a [i] [j + 1] <= 1

Օրինակ  

4 4
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
4

Բացատրությունը. Վերոնշյալ օրինակում 4-րդ շարքը պարունակում է 1-ի առավելագույն թիվը, այսինքն ՝ չորս 1-ը:

Ալգորիթմ  

Այս մեթոդով հիմնական գաղափարը յուրաքանչյուր շարքում երկուական որոնում կատարելն է և գտնել այն ինդեքսը, որտեղ 1-ն է տեղի ունեցել առաջին անգամ: Ելքն այն շարքն է, որն ունի նվազագույն ինդեքսի արժեք:

1. Անցնել մատրիցայի բոլոր շարքերում:

2. Յուրաքանչյուր շարքի համար կատարեք երկուական որոնում և գտեք այդ շարքում 1-ի առաջին դեպքի ինդեքսը:
Երկուական որոնում

  • Եթե ​​միջին տարրը 1 է, իսկ 1-ի միջինը `0, ապա վերադարձիր միջին ինդեքսը:
  • Եթե ​​միջին տարրը 0 է, ապա կատարեք երկուական որոնում աջ կեսում, այսինքն ՝ + 1-ից կեսից մինչև n:
  • այլապես, երկուական որոնում կատարեք ձախ կեսում, այսինքն `0-ից մինչև 1-ի կեսեր:
Տես նաեւ,
Fizz Buzz Leetcode

3. Վերադարձեք այն տողը, որն ունի նվազագույն ցուցանիշ:

Իրականացման  

C ++ ծրագիր ՝ 1-ի առավելագույն թվով շարքը գտնելու համար

#include <bits/stdc++.h>
using namespace std;

int first(vector<int> v, int low, int high) 
{ 
  if(high >= low) 
  { 
    int mid = low+(high-low)/2; 
    if((mid==0||v[mid-1]==0)&&v[mid]==1) 
    {
        return mid;
    }
    else if(v[mid]==0) 
    {
        return first(v,mid+1,high);
    }
    else
    {
        return first(v,low,mid-1);
    }
  } 
  return -1; 
} 

int find_row(vector<vector<int> > v) 
{ 
    int n = v.size();
    int m = v[0].size();
    int max_row_index = 0, max = -1; 
    int index; 
  for(int i=0;i<n;i++) 
  { 
    index = first(v[i],0,m-1); 
    if((index!=-1) && (m-index>max)) 
    { 
      max = m-index; 
      max_row_index = i; 
    } 
  } 
  return max_row_index+1; 
} 

int main() 
{ 
    int n,m;
    cin>>n>>m;
    vector<vector<int> > v;
    for(int i=0;i<n;i++)
    {
        vector<int> temp;
        for(int j=0;j<m;j++)
        {
            int x;
            cin>>x;
            temp.push_back(x);
        }
        v.push_back(temp);
    }
  cout<<find_row(v); 
  return 0; 
} 

Java ծրագիրը ՝ 1-ի առավելագույն թվով տողը գտնելու համար

import java.util.Random;
import java.util.Scanner;
class sum
{
    static int first(int v[], int low, int high)
    {
        if(high >= low) 
  { 
    int mid = low+(high-low)/2; 
    if((mid==0||v[mid-1]==0)&&v[mid]==1) 
    {
        return mid;
    }
    else if(v[mid]==0) 
    {
        return first(v,mid+1,high);
    }
    else
    {
        return first(v,low,mid-1);
    }
  } 
  return -1;
    }
    
    static int find_row(int a[][], int n, int m) 
    { 
  int max_row_index = 0, max = -1; 
  int index; 
  for(int i=0;i<n;i++) 
  { 
    index = first(a[i],0,m-1); 
    if((index!=-1) && (m-index>max)) 
    { 
      max = m-index; 
      max_row_index = i; 
    } 
  } 
  return max_row_index+1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[][] = new int[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                a[i][j] = sr.nextInt();
            }
        }
        int ans = find_row(a,n,m);
        System.out.println(ans);
    }
}
4 4
0 0 1 1
0 1 1 1
0 0 0 1 
0 0 1 1
2

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n * logm) որտեղ n տողերի քանակն է, իսկ m սյունակների քանակը: Այստեղ մենք կիրառում ենք երկուական որոնում յուրաքանչյուր տողում, ինչը մեզ տանում է դեպի nlogm ժամանակի բարդություն:

Տիեզերական բարդություն

Ո (1) քանի որ մենք այստեղ ոչ մի օժանդակ տարածք չենք ստեղծում, քանի որ այստեղ մեծ տվյալներ չենք պահում: